Current implementation: malloc loops trough all the holes in the freelist, checking if there is a hole with exactly the right size (len), in which case it takes the hole and returns it. While looping it also notes down the size of the smallest hole it has found that is still big enough (size > len). If it cannot find a hole with exactly the right size, it will use this noted hole. But because it only noted the size of the hole, it loops through all the holes again until it has found a hole with that size, then uses that hole.
Improvement: By not only noting down the size of the smallest hole, but also noting its addrress, the second loop is not necessary anymore. The cost: 2 more pointers are needed (both the found hole and the hole before it must be remembered), so it might add 4 pushes at the beginning and 4 pops at the end of the function. In the first loop two movw's are needed to note down the hole address, which are executed everytime a smaller hole is found. The gain: The whole second loop can be removed, which saves much program space (whole malloc becomes about 10% smaller) and even more execution time. By the way, I also found a little problem with malloc that occurs when __malloc_heap_end has not been defined (quite normal), so cp = STACK_POINTER() - __malloc_margin is used as heap end, and the available space is calculated as avail = cp - __brkval; If the stack pointer would have become lower than __brkval + __malloc_margin, then avail (being a size_t) would become less than zero = very much, so malloc would allocate the space which belongs to the stack. This can happen easily when the heap is filled (almost) up to the stackpointer - __malloc_margin, then just one or maybe a few pushes are done so there is less than __malloc_margin between heap end and stackpointer, and then malloc is called. I suggest the cp and __brkval should first be compared: if (cp < __brkval) return 0; or avail could be a signed integer (which is no problem as long as there is less than 32KB of memory); note that this fix is *not* included in the attached patch. Gerben
--- malloc.old.c 2008-06-20 17:25:08.000000000 +0200
+++ malloc.new.c 2008-06-20 17:32:00.000000000 +0200
@@ -65,7 +65,7 @@
void *
malloc(size_t len)
{
- struct __freelist *fp1, *fp2;
+ struct __freelist *fp1, *fp2, *sfp1, *sfp2;
char *cp;
size_t s, avail;
@@ -81,13 +81,14 @@
/*
* First, walk the free list and try finding a chunk that
* would match exactly. If we found one, we are done. While
- * walking, note down the size of the largest chunk we found
- * that would still fit the request -- we need it for step 2.
- *
+ * walking, note down the smallest chunk we found that would
+ * still fit the request -- we need it for step 2.
*/
for (s = 0, fp1 = __flp, fp2 = 0;
fp1;
fp2 = fp1, fp1 = fp1->nx) {
+ if (fp1->sz < len)
+ continue;
if (fp1->sz == len) {
/*
* Found it. Disconnect the chunk from the
@@ -99,9 +100,13 @@
__flp = fp1->nx;
return &(fp1->nx);
}
- if (fp1->sz > len) {
- if (s == 0 || fp1->sz < s)
+ else {
+ if (s == 0 || fp1->sz < s) {
+ /* this is the smallest chunk found so far */
s = fp1->sz;
+ sfp1 = fp1;
+ sfp2 = fp2;
+ }
}
}
/*
@@ -115,44 +120,33 @@
* and use the entire chunk.
*/
if (s) {
- if (s - len < sizeof(struct __freelist))
- len = s;
- for (fp1 = __flp, fp2 = 0;
- fp1;
- fp2 = fp1, fp1 = fp1->nx) {
- if (fp1->sz == s) {
- if (len == s) {
- /*
- * Use entire chunk; same as
- * above.
- */
- if (fp2)
- fp2->nx = fp1->nx;
- else
- __flp = fp1->nx;
- return &(fp1->nx);
- }
- /*
- * Split them up. Note that we leave
- * the first part as the new (smaller)
- * freelist entry, and return the
- * upper portion to the caller. This
- * saves us the work to fix up the
- * freelist chain; we just need to
- * fixup the size of the current
- * entry, and note down the size of
- * the new chunk before returning it
- * to the caller.
- */
- cp = (char *)fp1;
- s -= len;
- cp += s;
- fp2 = (struct __freelist *)cp;
- fp2->sz = len;
- fp1->sz = s - sizeof(size_t);
- return &(fp2->nx);
- }
+ if (s - len < sizeof(struct __freelist)) {
+ /* Disconnect it from freelist and return it. */
+ if (sfp2)
+ sfp2->nx = sfp1->nx;
+ else
+ __flp = sfp1->nx;
+ return &(sfp1->nx);
}
+ /*
+ * Split them up. Note that we leave
+ * the first part as the new (smaller)
+ * freelist entry, and return the
+ * upper portion to the caller. This
+ * saves us the work to fix up the
+ * freelist chain; we just need to
+ * fixup the size of the current
+ * entry, and note down the size of
+ * the new chunk before returning it
+ * to the caller.
+ */
+ cp = (char *)sfp1;
+ s -= len;
+ cp += s;
+ sfp2 = (struct __freelist *)cp;
+ sfp2->sz = len;
+ sfp1->sz = s - sizeof(size_t);
+ return &(sfp2->nx);
}
/*
* Step 3: If the request could not be satisfied from a
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ AVR-libc-dev mailing list AVR-libc-dev@nongnu.org http://lists.nongnu.org/mailman/listinfo/avr-libc-dev
