httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Charles Randall <>
Subject RE: [patch] smarter free block allocation to fix leak
Date Thu, 05 Aug 1999 17:06:12 GMT
Isn't this a classic "first-fit" vs "best-fit" memory allocation issue?

Is the memory savings really worth the extra CPU? 

Knuth suggests first-fit in Section 2.5, "Dynamic Storage Allocation" of
Fundamental Algorithms (right before presenting Algorithm A he says, "For
these reasons the first-fit method can be recommended").

Sounds like you're examining a pathological case. Should this be a tunable
parameter instead?

Perhaps a bucketed approach with separate free-lists for separate allocation
sizes to get you "in the ballpark" (with first-fit within the bucket) would
be better. This is what Doug Lea's G++ malloc does.


-----Original Message-----
From: David Harris []
Sent: Thursday, August 05, 1999 10:38 AM
Subject: [patch] smarter free block allocation to fix leak

I've been chasing memory leaks in mod_ssl (actually I think they are in
right now) and, in doing that, I've bumped into a few memory leaks in
The first one I've already described and posted with a patch to the list.

This one deals with the behavior of the main/alloc.c:new_block() command.
receiving a request for a new block it first searches through the
block_freelist to find a block of an acceptable size and then, if none
it has a new block allocated. The problem is that it returns the first block
an acceptable size that it finds on the block_freelist, which causes
when not all the blocks are the same size. It really needs to search for the
smallest block which is of an acceptable size. Here is why:

Lets say that you have two pools. A and B. Pool A is going to have ten
allocations of 6k, while pool B is going to have one allocation of 1mb.
you allocate the ten 6k blocks for pool A, which, I think, really creates
8k blocks. Then pool B receives its 1mb allocation, and it allocates a 1mb
block. Then you clear all of the pools which places all the blocks back on
block_freelist. Then re-allocate memory from the pools in the same manner:
A receives 10 allocation requests for 6k, and asks new_block() for ten 8k
blocks. The problem is that new_block() may very well return the 1mb block
satisfy a small request from pool A. Then when pool B asks for a 1mb block,
new one will have to be allocated.

I've actually seen this happen in my tracing of Apache+mod_ssl.. where
allocated some large blocks which then, after a graceful restart and
back on the block_freelist, got handed out to pools which didn't need them,
when the large allocation came back up again, a new block had to be

This patch simply makes new_block() return the smallest possible block from
block_freelist that would satisfy the request for a new block. This way
blocks on the block_freelist don't get handed out to pools that don't need

 - David Harris
   Principal Engineer, DRH Internet Services

diff -r -u3 apache_1.3.6_orig/src/main/alloc.c
--- apache_1.3.6_orig/src/main/alloc.c  Wed Aug  4 12:05:12 1999
+++ apache_1.3.6_blockalloc/src/main/alloc.c    Wed Aug  4 13:45:55 1999
@@ -314,23 +314,40 @@
     union block_hdr **lastptr = &block_freelist;
     union block_hdr *blok = block_freelist;
+    int blok_size;
+    union block_hdr **best_lastptr = NULL;
+    union block_hdr *best_blok = NULL;
+    int best_blok_size = 0;

     /* First, see if we have anything of the required size
-     * on the free list...
+     * on the free list... (and make sure to get the smallest
+     * possible one from the free list)

     while (blok != NULL) {
-       if (min_size + BLOCK_MINFREE <= blok->h.endp - blok->h.first_avail)
-           *lastptr = blok->;
-           blok-> = NULL;
-           debug_verify_filled(blok->h.first_avail, blok->h.endp,
-               "Ouch!  Someone trounced a block on the free list!\n");
-           return blok;
+       blok_size = blok->h.endp - blok->h.first_avail;
+       if (min_size + BLOCK_MINFREE <= blok_size &&
+            (best_blok == NULL || blok_size < best_blok_size))
+        {
+            best_blok_size = blok_size;
+            best_blok = blok;
+            best_lastptr = lastptr;
+            if (blok_size == min_size + BLOCK_MINFREE)
+               break;
        else {
            lastptr = &blok->;
            blok = blok->;
+    }
+    if (best_blok != NULL) {
+       *best_lastptr = best_blok->;
+       best_blok-> = NULL;
+       debug_verify_filled(best_blok->h.first_avail, best_blok->h.endp,
+           "Ouch!  Someone trounced a block on the free list!\n");
+       return best_blok;

     /* Nope. */

View raw message