Re[2]: [avr-libc-dev] malloc implementation

[Bertolt Mildner]

Hi Joerg,


???? You really mean that seriously ????

>> I just had a quick look at malloc.c and saw that in step 2 the free
>> list is walked through a second time.

>> Why is this necessary when in step 1 the smallest fitting chunk has
>> already been found?

> See the comments (for step 2).  Btw., I just notice a minor mistake in
> the comment in step 1: of course, the *smallest* chunk that would
> still fit the request is recorded, not the largest one.

> The second walk is necessary as the smallest fitting entry needs to be
> split up, and disconnected from the list.  While we still have the
> size of this chunk (recorded from step 1), we have to find its
> position in the list again.  As it is a single linked list, you can
> only change entries while walking the list.

Why should a single linked list, in general, require a second walk for
entry removal or entry manipulation?

Why should splitting require a second walk?

> Step 1 can only do its job immediately (and thus stop walking at once)
> if the size fits exactly, as this is the optimal entry that could be
> found.  If the ``best fit'' is not an exact match, you don't know that
> for sure initially.

Why "it" has to be done immediately in the loop?

Why knowing if a candidate is the best match should have to be known
immediately?

> The idea of the two-step algorithm is to always return exactly fitting
> junks if possible, to avoid memory fragmentation.

Why do you think this requires a second walk?


The worst case complexity of this implementation is O(2*x) while one
could have O(x) with only investing two more pointers on the stack.

Even worse, as free() tries to rejoin chunks, malloc() may regularly
hit the split case!

I strongly believe that a exact match should be view as a (rare) corner case.


*UNTESTED CODE*

void *
malloc(size_t len)
{
        struct __freelist *current          = __flp;
        struct __freelist *before_current   = NULL;
        struct __freelist *candidate        = NULL;
        struct __freelist *before_candidate = NULL;

        size_t size = 0;
        char *cp;
        
        /*
         * Our minimum chunk size is the size of a pointer (plus the
         * size of the "sz" field, but we don't need to account for
         * this), otherwise we could not possibly fit a freelist entry
         * into the chunk later.
         */
        if (len < sizeof(struct __freelist) - sizeof(size_t))
                len = sizeof(struct __freelist) - sizeof(size_t);


        /*
         * Step 1: Walk the free list and try finding the smallest
         * chunk that is >= len.
         * While walking, note down the candidate (incl. its previous
         * entry). Stop walking if we found an exact match or if we
         * hit the end of the free list.
         * If we have a candidate we use it and probably split it.
         * If no candidate was found we continue in step 2.
         *
         */
        while ((current != NULL) && (size != len))
        {
          if ((current->sz >= len) &&
              ((current->sz == len) ||
               (size == 0) ||
               ((size != 0) &&
                (size > current->sz))))
          {
            candidate = current;
            before_candidate = before_current;
            size = current->sz;
          }

          before_current = current;
          current = current->nx;
        }

        if (candadate != NULL) /* found one with sz >= len */
        {
          if ((size == len) || /* full match or */
              (size - len < sizeof(struct __freelist))) /* too small to split*
          {
            if (before_candidate == NULL) /* match if first in list*/
            {
              __flp = candidate->nx;
            }
            else
            {
              before_candidate->nx = candidate->nx;
            }

            return &(candidate->nx);
          }
          else /* split current */
          {
            /* resize remaining entry */
            candidate->sz -= len + sizeof(struct __freelist.sz);

            /* create chunk to be returnd */
            cp = ((char*) (&candidate->nx)) + candidate->sz;
            current = (struct __freelist*) cp;
              
            current->sz = len;

            return &(current->nx);
          }
        }

        /*
         * Step 2: If the request could not be satisfied from a
         * freelist entry, just prepare a new chunk.  This means we
         * need to obtain more memory first.  The largest address just
         * not allocated so far is remembered in the brkval variable.
         * Under Unix, the "break value" was the end of the data
         * segment as dynamically requested from the operating system.
         * Since we don't have an operating system, just make sure
         * that we don't collide with the stack.
         */
        if (__brkval == 0)
                __brkval = __malloc_heap_start;
        cp = __malloc_heap_end;
        if (cp == 0)
                cp = STACK_POINTER() - __malloc_margin;
        size = cp - __brkval;
        /*
         * Both tests below are needed to catch the case len >= 0xfffe.
         */
        if (size >= len && size >= len + sizeof(size_t)) {
                current = (struct freelist *)__brkval;
                __brkval += len + sizeof(size_t);
                current->sz = len;
                return &(current->nx);
        }
        /*
         * Step 4: There's no help, just fail. :-/
         */
        return 0;
}

BTW: as one size_t could be saved this basicly boils down to one more
pointer on the stack.

Bertolt

-- 
Best regards,
 Bertolt                            mailto:address@hidden