[En-Nut-Discussion] NutHeapAlloc Error?

[Timothy M. De Baillie]

Timothy M. De Baillie wrote:
> We found the error. Solution coming out soon..

Found in Stable OS Versions 4.4.0 -> 4.6.4
On the ARM processors

Description of Bug:
If your malloc (NutHeapAlloc) finds the last heap to be the "best" fit
for your request and it can't be split (there's not enough additional
space in the heap after the bytes you requested and the heap size and
DEADBEEF for another "usable" heap), the resulting malloc size can be of
"odd" (not on 4 byte boundary) size, which causes the malloc to fail
when the DEADBEEF is written on a non-word boundary.  This results in
the SAM7 going into ABORT mode, which then the watchdog will catch.

Solution:
Make sure that when you don't split, you set the size of the heap to a 4
byte boundary.

Additional potential bug:
The malloc isn't checked for available memory after the argument is
incremented by MEMOVHD.

Solution:
Move the check for available memory below the increment by MEMOVHD.



Here is the NutHeapAlloc (os/heap.c) with the changes:

~~~begin NutHeapAlloc~~~

void *NutHeapAlloc(size_t size)
{
     HEAPNODE *node;
     HEAPNODE **npp;
     HEAPNODE *fit = 0;
     HEAPNODE **fpp = 0;

#if defined(ARCH_32BIT)
     /*
      * Allign to the word boundary
      */
     while ((size & 0x03) != 0)
         size++;
#endif

     /*
      * We need additional space in front of the allocated memory
      * block to store its size. If this is still less than the
      * space required by a free node, increase it.
      */
     if ((size += MEMOVHD) < sizeof(HEAPNODE))
         size = sizeof(HEAPNODE);

//CHANGE, this is moved from before the above if
     if (size >= available) {
#ifdef NUTDEBUG
         if (__heap_trf)
             fputs("MEMOVR\n", __heap_trs);
#endif
         return 0;
     }
//end CHANGE

     /*
      * Walk through the linked list of free nodes and find the best fit.
      */
     node = heapFreeList;
     npp = (HEAPNODE **) & heapFreeList;
     while (node) {

         /*
          * Found a note that fits?
          */
         if (node->hn_size >= size) {
             /*
              * If it's an exact match, we don't
              * search any further.
              */
             if (node->hn_size == size) {
                 fit = node;
                 fpp = npp;
                 break;
             }

             /*
              * Is it the first one we found
              * or was the previous one larger?
              */
             if (fit == 0 || (fit->hn_size > node->hn_size)) {
                 fit = node;
                 fpp = npp;
             }
         }
         npp = &node->hn_next;
         node = node->hn_next;
     }

     if (fit) {
         /*
          * If the node we found is larger than the
          * required space plus the space needed for
          * a new node plus a defined threshold, then
          * we split it.
          */
         if (fit->hn_size > size + sizeof(HEAPNODE) + ALLOC_THRESHOLD) {
             node = (HEAPNODE *) ((uptr_t) fit + size);
             node->hn_size = fit->hn_size - size;
             node->hn_next = fit->hn_next;
             fit->hn_size = size;
             *fpp = node;
         } else {
//CHANGE, replaced else
             *fpp = fit->hn_next;
             fit->hn_size &= 0xfffffffc; //this makes sure we hit a 4
byte boundary on the DEADBEEF write
         }
//end CHANGE

         available -= fit->hn_size;
         setBeef(fit);
         fit = (HEAPNODE *) & fit->hn_next;
     }
#ifdef NUTDEBUG
     if (__heap_trf) {
         fprintf(__heap_trs, "\n[H%x,A%d/%d] ", (u_int)(uptr_t) fit,
(int)(((HEAPNODE *) (((uptr_t *) fit) - 1))->hn_size), (int)size);
     }
#endif
     return fit;
}

~~~end NutHeapAlloc~~~

This fixed our issues and appears to be a rather important bug fix,
especially in systems that utilize dynamic memory allocation.  This can
be exercised if you have a chopped/fragmented heap (a garbage collector 
would help, but be potentially costly) or use nearly ALL of your memory 
at any point in time.

If someone could implement these on the SVN Head, that would be much
appreciated.

Thanks,
Tim DeBaillie