从K＆R书中解释malloc的这种实现
这是Kernighan和Ritchie关于C的书的摘录。 它显示了如何实现malloc一个版本。 虽然评论很好，但我很难理解它。 有人可以解释一下吗？
typedef long Align; /* for alignment to long boundary */ union header { /* block header */ struct { union header *ptr; /* next block if on free list */ unsigned size; /* size of this block */ } s; Align x; /* force alignment of blocks */ }; typedef union header Header; static Header base; /* empty list to get started */ static Header *freep = NULL; /* start of free list */ /* malloc: general-purpose storage allocator */ void *malloc(unsigned nbytes) { Header *p, *prevp; Header *morecore(unsigned); unsigned nunits; nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1; if ((prevp = freep) == NULL) { /* no free list yet */ base.s.ptr = freeptr = prevptr = &base; base.s.size = 0; } for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) { if (p->s.size >= nunits) { /* big enough */ if (p->s.size == nunits) /* exactly */ prevp->s.ptr = p->s.ptr; else { /* allocate tail end */ p->s.size -= nunits; p += p->s.size; p->s.size = nunits } freep = prevp; return (void *)(p+1); } if (p == freep) /* wrapped around free list */ if ((p = morecore(nunits)) == NULL) return NULL; /* none left */ } } #define NALLOC 1024 /* minimum #units to request */ /* morecore: ask system for more memory */ static Header *morecore(unsigned nu) { char *cp, *sbrk(int); Header *up; if (nu s.size = nu; free((void *)(up+1)); return freep; } /* free: put block ap in free list */ void free(void *ap) { Header *bp, *p; bp = (Header *)ap - 1; /* point to block header */ for (p = freep; !(bp > p && bp s.ptr); p = p->s.ptr) if (p >= p->s.ptr && (bp > p || bp s.ptr)) break; /* freed block at start or end of arena */ if (bp + bp->size == p->s.ptr) { bp->s.size += p->s.ptr->s.size; bp->s.ptr = p->s.ptr->s.ptr; } else bp->s.ptr = p->s.ptr; if (p + p->size == bp) { p->s.size += bp->s.size; p->s.ptr = bp->s.ptr; } else p->s.ptr = bp; freep = p; }
好吧，我们这里有一大堆写得很糟糕的代码。 我将在这篇文章中做的最好被描述为软件考古学。
第1步：修复格式。
缩进和紧凑的格式对任何人都没有好处。 需要插入各种空格和空行。 评论可以用更易读的方式编写。 我将从修复它开始。
与此同时，我正在改变K＆R款式的支撑款式 – 请注意K＆R支架款式是可以接受的，这仅仅是我个人的偏好。 另一个个人偏好是在指向的类型旁边写指针。 我不会在这里争论（主观）风格问题。
此外， Header的类型定义是完全不可读的，它需要一个彻底的修复。
我发现了一些完全模糊不清的东西：它们似乎在函数内声明了一个函数原型。 Header* morecore(unsigned); 。 这是非常古老和非常糟糕的风格，我不确定C甚至是否允许它。 让我们删除该行，无论该函数做什么，都必须在别处定义。
typedef long Align; /* for alignment to long boundary */ typedef union header /* block header */ { struct { union header *ptr; /* next block if on free list */ unsigned size; /* size of this block */ } s; Align x; /* force alignment of blocks */ } Header; static Header base; /* empty list to get started */ static Header* freep = NULL; /* start of free list */ /* malloc: general-purpose storage allocator */ void* malloc (unsigned nbytes) { Header* p; Header* prevp; unsigned nunits; nunits = (nbytes + sizeof(Header) - 1) / sizeof(header) + 1; if ((prevp = freep) == NULL) /* no free list yet */ { base.s.ptr = freeptr = prevptr = &base; base.s.size = 0; } for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) { if (p->s.size >= nunits) /* big enough */ { if (p->s.size == nunits) /* exactly */ prevp->s.ptr = p->s.ptr; else /* allocate tail end */ { p->s.size -= nunits; p += p->s.size; p->s.size = nunits } freep = prevp; return (void *)(p+1); } if (p == freep) /* wrapped around free list */ if ((p = morecore(nunits)) == NULL) return NULL; /* none left */ } }
好了，我们实际上可以读取代码。
第二步：清除广泛认可的不良做法。
这段代码充满了现在被认为是不好的做法。 它们需要被删除，因为它们会危及代码的安全性，可读性和维护性。 如果您想要提及与我一样的做法，请查看广泛认可的编码标准MISRA-C 。
我发现并删除了以下不良做法：
1）只是在代码中键入unsigned可能会导致混淆：这是程序员的错字还是打算写unsigned int ？ 我们应该用unsigned int替换所有unsigned 。 但是，当我们这样做时，我们发现它在此上下文中用于给出各种二进制数据的大小。 用于此类事项的正确类型是C标准类型size_t 。 这基本上只是一个unsigned int，但它保证对特定平台来说“足够大”。 sizeof运算符返回size_t类型的结果，如果我们查看C标准对真实malloc的定义，则它是void *malloc(size_t size); 。 所以size_t是最正确的类型。
2）对于我们自己的malloc函数使用与stdlib.h中相同的名称是一个坏主意。 如果我们需要包含stdlib.h，事情会变得混乱。 根据经验，永远不要在自己的代码中使用C标准库函数的标识符名称。 我将名称更改为kr_malloc。
3）代码滥用了所有静态变量保证初始化为零的事实。 这是由C标准明确定义的，但却是一个相当微妙的规则。 让我们明确地初始化所有静态，以表明我们没有忘记偶然启动它们。
4）内部条件的分配是危险的，难以阅读。 如果可能，应该避免这种情况，因为它也可能导致错误，例如classic = vs == bug。
5）由于评估的顺序，同一行上的多个分配难以阅读，也可能是危险的。
6）同一行上的多个声明很难阅读，也很危险，因为混合数据和指针声明时可能会导致错误。 始终在每行上声明每个变量。
7）在每个语句后总是使用大括号。 不这样做会导致bug错误。
8）永远不要将特定指针类型的强制类型转换为void *。 它在C中是不必要的，并且可以隐藏编译器本来会检测到的错误。
9）避免在函数内使用多个return语句。 有时他们会导致更清晰的代码，但在大多数情况下，他们会导致意大利面。 正如代码所代表的那样，我们不能在不重写循环的情况下改变它，所以我稍后会修复它。
10）保持循环简单。 它们应该包含一个init语句，一个循环条件和一个迭代，没有别的。 这个for循环，使用逗号运算符和所有内容，非常模糊。 同样，我们发现需要将此循环重写为理智的东西。 我接下来会这样做，但现在我们有：
typedef long Align; /* for alignment to long boundary */ typedef union header /* block header */ { struct { union header *ptr; /* next block if on free list */ size_t size; /* size of this block */ } s; Align x; /* force alignment of blocks */ } Header; static Header base = {0}; /* empty list to get started */ static Header* freep = NULL; /* start of free list */ /* malloc: general-purpose storage allocator */ void* kr_malloc (size_t nbytes) { Header* p; Header* prevp; size_t nunits; nunits = (nbytes + sizeof(Header) - 1) / sizeof(header) + 1; prevp = freep; if (prevp == NULL) /* no free list yet */ { base.s.ptr = &base; freeptr = &base; prevptr = &base; base.s.size = 0; } for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) { if (p->s.size >= nunits) /* big enough */ { if (p->s.size == nunits) /* exactly */ { prevp->s.ptr = p->s.ptr; } else /* allocate tail end */ { p->s.size -= nunits; p += p->s.size; p->s.size = nunits } freep = prevp; return p+1; } if (p == freep) /* wrapped around free list */ { p = morecore(nunits); if (p == NULL) { return NULL; /* none left */ } } } /* for */ }
第3步：重写模糊循环。
由于前面提到的原因。 我们可以看到这个循环永远持续，它通过从函数返回来终止，无论是在分配完成时，还是在没有内存的情况下。 因此，我们将其创建为循环条件，然后将返回函数提升到函数的末尾。 让我们摆脱那个丑陋的逗号运算符。
我将介绍两个新变量：一个用于保存结果指针的结果变量，另一个用于跟踪循环是否应该继续。 我将通过使用bool类型来bool K＆R的思想，这是自1999年以来C语言的一部分。
（我希望我没有用这个改变改变算法，我相信我没有）
#include typedef long Align; /* for alignment to long boundary */ typedef union header /* block header */ { struct { union header *ptr; /* next block if on free list */ size_t size; /* size of this block */ } s; Align x; /* force alignment of blocks */ } Header; static Header base = {0}; /* empty list to get started */ static Header* freep = NULL; /* start of free list */ /* malloc: general-purpose storage allocator */ void* kr_malloc (size_t nbytes) { Header* p; Header* prevp; size_t nunits; void* result; bool is_allocating; nunits = (nbytes + sizeof(Header) - 1) / sizeof(header) + 1; prevp = freep; if (prevp == NULL) /* no free list yet */ { base.s.ptr = &base; freeptr = &base; prevptr = &base; base.s.size = 0; } is_allocating = true; for (p = prevp->s.ptr; is_allocating; p = p->s.ptr) { if (p->s.size >= nunits) /* big enough */ { if (p->s.size == nunits) /* exactly */ { prevp->s.ptr = p->s.ptr; } else /* allocate tail end */ { p->s.size -= nunits; p += p->s.size; p->s.size = nunits } freep = prevp; result = p+1; is_allocating = false; /* we are done */ } if (p == freep) /* wrapped around free list */ { p = morecore(nunits); if (p == NULL) { result = NULL; /* none left */ is_allocating = false; } } prevp = p; } /* for */ return result; }
第4步：编译这个垃圾。
由于这是来自K＆R，它充满了拼写错误。 sizeof(header)应该是sizeof(Header) 。 缺少分号。 他们使用不同的名称freep，prevp与freeptr，prevptr，但显然意味着相同的变量。 我相信后者实际上是更好的名字，所以让我们使用它们。
#include typedef long Align; /* for alignment to long boundary */ typedef union header /* block header */ { struct { union header *ptr; /* next block if on free list */ size_t size; /* size of this block */ } s; Align x; /* force alignment of blocks */ } Header; static Header base = {0}; /* empty list to get started */ static Header* freeptr = NULL; /* start of free list */ /* malloc: general-purpose storage allocator */ void* kr_malloc (size_t nbytes) { Header* p; Header* prevptr; size_t nunits; void* result; bool is_allocating; nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1; prevptr = freeptr; if (prevptr == NULL) /* no free list yet */ { base.s.ptr = &base; freeptr = &base; prevptr = &base; base.s.size = 0; } is_allocating = true; for (p = prevptr->s.ptr; is_allocating; p = p->s.ptr) { if (p->s.size >= nunits) /* big enough */ { if (p->s.size == nunits) /* exactly */ { prevptr->s.ptr = p->s.ptr; } else /* allocate tail end */ { p->s.size -= nunits; p += p->s.size; p->s.size = nunits; } freeptr = prevptr; result = p+1; is_allocating = false; /* we are done */ } if (p == freeptr) /* wrapped around free list */ { p = morecore(nunits); if (p == NULL) { result = NULL; /* none left */ is_allocating = false; } } prevptr = p; } /* for */ return result; }
现在我们有一些可读，可维护的代码，没有很多危险的做法，甚至可以编译！ 所以现在我们真的可以开始思考代码实际上在做什么了。
正如您可能已经猜到的那样，结构“Header”是链接列表中节点的声明。 每个这样的节点都包含指向下一个节点的指针。 我不太了解morecore函数，也没有“环绕”，我从来没有使用过这个函数，也没有使用sbrk 。 但我假设它分配了此结构中指定的标头，以及该标头后面的一些原始数据块。 如果是这样，那就解释了为什么没有实际的数据指针：假设数据在内存中相邻的标题之后。 因此，对于每个节点，我们得到标头，然后我们在标头后面获得一大块原始数据。
迭代本身非常简单，它们通过单链表，一次一个节点。
在循环结束时，他们将指针设置为超过“块”结尾的第一点，然后将其存储在静态变量中，以便程序在下次调用函数时记住它先前分配内存的位置。
他们正在使用一种技巧使其标题最终位于对齐的内存地址上：它们将所有开销信息与一个足够大的变量存储在一个联合中，以对应平台的对齐要求。 因此，如果“ptr”的大小加上“size”的大小太小而无法给出精确对齐，则union保证至少分配sizeof（Align）字节。 我相信今天整个技巧已经过时，因为C标准要求自动结构/联合填充。
我正在研究K＆R，就像我想象OP在他问这个问题的时候，我来到这里是因为我也发现这些实现令人困惑。 虽然接受的答案非常详细和有用，但我试图采用不同的方法来理解最初编写的代码 – 我已经完成了代码，并在代码的各个部分添加了注释，这对我来说很难。 这包括该部分中其他例程的代码（这些函数是free和memcore – 我已将它们重命名为kandr_malloc和kandr_free以避免与stdlib冲突）。 我想我会把这个留在这里作为接受答案的补充，对于其他可能觉得有帮助的学生。
我承认此代码中的注释过多。 请知道我只是在做这个学习练习，我并不是说这是实际编写代码的好方法。
我冒昧地将一些变量名称改为对我来说更直观的变量名称; 除此之外，代码基本上保持不变。 虽然valgrind对某些应用程序抱怨，但它似乎可以编译并运行我使用的测试程序。
另外：评论中的一些文字直接取自K＆R或手册页 – 我不打算对这些部分给予任何赞扬。
#include // sbrk #define NALLOC 1024 // Number of block sizes to allocate on call to sbrk #ifdef NULL #undef NULL #endif #define NULL 0 // long is chosen as an instance of the most restrictive alignment type typedef long Align; /* Construct Header data structure. To ensure that the storage returned by * kandr_malloc is aligned properly for the objects that are stored in it, all * blocks are multiples of the header size, and the header itself is aligned * properly. This is achieved through the use of a union; this data type is big * enough to hold the "widest" member, and the alignment is appropriate for all * of the types in the union. Thus by including a member of type Align, which * is an instance of the most restrictive type, we guarantee that the size of * Header is aligned to the worst-case boundary. The Align field is never used; * it just forces each header to the desired alignment. */ union header { struct { union header *next; unsigned size; } s; Align x; }; typedef union header Header; static Header base; // Used to get an initial member for free list static Header *freep = NULL; // Free list starting point static Header *morecore(unsigned nblocks); void kandr_free(void *ptr); void *kandr_malloc(unsigned nbytes) { Header *currp; Header *prevp; unsigned nunits; /* Calculate the number of memory units needed to provide at least nbytes of * memory. * * Suppose that we need n >= 0 bytes and that the memory unit sizes are b > 0 * bytes. Then n / b (using integer division) yields one less than the number * of units needed to provide n bytes of memory, except in the case that n is * a multiple of b; then it provides exactly the number of units needed. It * can be verified that (n - 1) / b provides one less than the number of units * needed to provide n bytes of memory for all values of n > 0. Thus ((n - 1) * / b) + 1 provides exactly the number of units needed for n > 0. * * The extra sizeof(Header) in the numerator is to include the unit of memory * needed for the header itself. */ nunits = ((nbytes + sizeof(Header) - 1) / sizeof(Header)) + 1; // case: no free list yet exists; we have to initialize. if (freep == NULL) { // Create degenerate free list; base points to itself and has size 0 base.s.next = &base; base.s.size = 0; // Set free list starting point to base address freep = &base; } /* Initialize pointers to two consecutive blocks in the free list, which we * call prevp (the previous block) and currp (the current block) */ prevp = freep; currp = prevp->s.next; /* Step through the free list looking for a block of memory large enough to * fit nunits units of memory into. If the whole list is traversed without * finding such a block, then morecore is called to request more memory from * the OS. */ for (; ; prevp = currp, currp = currp->s.next) { /* case: found a block of memory in free list large enough to fit nunits * units of memory into. Partition block if necessary, remove it from the * free list, and return the address of the block (after moving past the * header). */ if (currp->s.size >= nunits) { /* case: block is exactly the right size; remove the block from the free * list by pointing the previous block to the next block. */ if (currp->s.size == nunits) { /* Note that this line wouldn't work as intended if we were down to only * 1 block. However, we would never make it here in that scenario * because the block at &base has size 0 and thus the conditional will * fail (note that nunits is always >= 1). It is true that if the block * at &base had combined with another block, then previous statement * wouldn't apply - but presumably since base is a global variable and * future blocks are allocated on the heap, we can be sure that they * won't border each other. */ prevp->s.next = currp->s.next; } /* case: block is larger than the amount of memory asked for; allocate * tail end of the block to the user. */ else { // Changes the memory stored at currp to reflect the reduced block size currp->s.size -= nunits; // Find location at which to create the block header for the new block currp += currp->s.size; // Store the block size in the new header currp->s.size = nunits; } /* Set global starting position to the previous pointer. Next call to * malloc will start either at the remaining part of the partitioned block * if a partition occurred, or at the block after the selected block if * not. */ freep = prevp; /* Return the location of the start of the memory, ie after adding one * so as to move past the header */ return (void *) (currp + 1); } // end found a block of memory in free list case /* case: we've wrapped around the free list without finding a block large * enough to fit nunits units of memory into. Call morecore to request that * at least nunits units of memory are allocated. */ if (currp == freep) { /* morecore returns freep; the reason that we have to assign currp to it * again (since we just tested that they are equal), is that there is a * call to free inside of morecore that can potentially change the value * of freep. Thus we reassign it so that we can be assured that the newly * added block is found before (currp == freep) again. */ if ((currp = morecore(nunits)) == NULL) { return NULL; } } // end wrapped around free list case } // end step through free list looking for memory loop } static Header *morecore(unsigned nunits) { void *freemem; // The address of the newly created memory Header *insertp; // Header ptr for integer arithmatic and constructing header /* Obtaining memory from OS is a comparatively expensive operation, so obtain * at least NALLOC blocks of memory and partition as needed */ if (nunits < NALLOC) { nunits = NALLOC; } /* Request that the OS increment the program's data space. sbrk changes the * location of the program break, which defines the end of the process's data * segment (ie, the program break is the first location after the end of the * uninitialized data segment). Increasing the program break has the effect * of allocating memory to the process. On success, brk returns the previous * break - so if the break was increased, then this value is a pointer to the * start of the newly allocated memory. */ freemem = sbrk(nunits * sizeof(Header)); // case: unable to allocate more memory; sbrk returns (void *) -1 on error if (freemem == (void *) -1) { return NULL; } // Construct new block insertp = (Header *) freemem; insertp->s.size = nunits; /* Insert block into the free list so that it is available for malloc. Note * that we add 1 to the address, effectively moving to the first position * after the header data, since of course we want the block header to be * transparent for the user's interactions with malloc and free. */ kandr_free((void *) (insertp + 1)); /* Returns the start of the free list; recall that freep has been set to the * block immediately preceeding the newly allocated memory (by free). Thus by * returning this value the calling function can immediately find the new * memory by following the pointer to the next block. */ return freep; } void kandr_free(void *ptr) { Header *insertp, *currp; // Find address of block header for the data to be inserted insertp = ((Header *) ptr) - 1; /* Step through the free list looking for the position in the list to place * the insertion block. In the typical circumstances this would be the block * immediately to the left of the insertion block; this is checked for by * finding a block that is to the left of the insertion block and such that * the following block in the list is to the right of the insertion block. * However this check doesn't check for one such case, and misses another. We * still have to check for the cases where either the insertion block is * either to the left of every other block owned by malloc (the case that is * missed), or to the right of every block owned by malloc (the case not * checked for). These last two cases are what is checked for by the * condition inside of the body of the loop. */ for (currp = freep; !((currp < insertp) && (insertp < currp->s.next)); currp = currp->s.next) { /* currp >= currp->s.ptr implies that the current block is the rightmost * block in the free list. Then if the insertion block is to the right of * that block, then it is the new rightmost block; conversely if it is to * the left of the block that currp points to (which is the current leftmost * block), then the insertion block is the new leftmost block. Note that * this conditional handles the case where we only have 1 block in the free * list (this case is the reason that we need >= in the first test rather * than just >). */ if ((currp >= currp->s.next) && ((currp < insertp) || (insertp < currp->s.next))) { break; } } /* Having found the correct location in the free list to place the insertion * block, now we have to (i) link it to the next block, and (ii) link the * previous block to it. These are the tasks of the next two if/else pairs. */ /* case: the end of the insertion block is adjacent to the beginning of * another block of data owned by malloc. Absorb the block on the right into * the block on the left (ie the previously existing block is absorbed into * the insertion block). */ if ((insertp + insertp->s.size) == currp->s.next) { insertp->s.size += currp->s.next->s.size; insertp->s.next = currp->s.next->s.next; } /* case: the insertion block is not left-adjacent to the beginning of another * block of data owned by malloc. Set the insertion block member to point to * the next block in the list. */ else { insertp->s.next = currp->s.next; } /* case: the end of another block of data owned by malloc is adjacent to the * beginning of the insertion block. Absorb the block on the right into the * block on the left (ie the insertion block is absorbed into the preceeding * block). */ if ((currp + currp->s.size) == insertp) { currp->s.size += insertp->s.size; currp->s.next = insertp->s.next; } /* case: the insertion block is not right-adjacent to the end of another block * of data owned by malloc. Set the previous block in the list to point to * the insertion block. */ else { currp->s.next = insertp; } /* Set the free pointer list to start the block previous to the insertion * block. This makes sense because calls to malloc start their search for * memory at the next block after freep, and the insertion block has as good a * chance as any of containing a reasonable amount of memory since we've just * added some to it. It also coincides with calls to morecore from * kandr_malloc because the next search in the iteration looks at exactly the * right memory block. */ freep = currp; }
malloc（）的基础
在Linux中，有两种典型的请求内存的方法： sbrk和mmap 。 这些系统调用对频繁的小分配有严重的限制。 malloc（）是一个解决此问题的库函数。 它使用sbrk / mmap请求大块内存，并在大块内部返回小内存块。 这比直接调用sbrk / mmap更有效，更灵活。
K＆R malloc（）
在K＆R实现中， 核心 （通常称为竞技场 ）是一大块内存。 morecore()通过sbrk()从系统请求核心。 当您多次调用malloc（）/ free（）时，将使用/分配核心中的某些块，而其他块则是空闲的。 K＆R malloc将空闲块的地址存储在循环单链表中。 在此列表中，每个节点都是一个空闲内存块。 第一个sizeof(Header)字节保持块的大小和指向下一个空闲块的指针。 空闲块中的其余字节未初始化。 与教科书中的典型列表不同，空闲列表中的节点只是指向核心中一些未使用区域的指针; 除了核心之外，您实际上并没有分配每个节点。 该列表是理解算法的关键。
下图显示了具有两个核心/竞技场的示例内存布局。 在图中，每个字符都采用sizeof(Header)字节。 @是一个Header ， +标记分配的内存和-标记内核中的空闲内存。 在该示例中，有三个分配的块和三个空闲块。 三个空闲块存储在循环列表中。 对于三个已分配的块，只有它们的大小存储在Header 。
This is core 1 This is core 2 @---------@+++++++++@++++++++++++ @----------@+++++++++++++++++@------------ | | | p->ptr->ptr p = p->ptr->ptr->ptr p->ptr
在您的代码中， freep是空闲列表的入口点。 如果你反复关注freep->ptr ，你会回到freep – 它是循环的。 一旦你理解了循环单链表，剩下的就相对简单了。 malloc()找到一个空闲块并可能将其拆分。 free()将一个空闲块添加回列表，并可以将其合并到相邻的空闲块。 他们都试图维护列表的结构。
关于实施的其他意见
-
代码注释在
malloc()提到“包裹”。 当您遍历整个空闲列表但找不到大于请求长度的空闲块时，会发生该行。 在这种情况下，您必须使用morecore()添加新核心。 -
base是一个零大小的块，始终包含在空闲列表中。 避免特殊套管是一种技巧。 这不是绝对必要的。 -
free()may look a little complex because it has to consider four different cases to merge a newly freed block to other free blocks in the list. This detail is not that important unless you want to reimplement by yourself. -
This blog post explains K&R malloc in more details.
PS: K&R malloc is one of the most elegant pieces of code in my view. It was really eye opening when I first understood the code. It makes me sad that some modern programmers, not even understanding the basic of this implementation, are calling the masterpiece crap solely based on its coding style.
I also found this exercise great and interesting.
In my opinion visualizing the structure may help a lot with understanding the logic – or at least this worked for me. Below is my code, which prints as much as possible about the flow of the K&R malloc.
The most significant change I made in the K&R malloc is the change of ‘free’ to make sure some old pointer will not be used again. Other than that I added comments and fixed some small typos.
Experimenting with NALLOC, MAXMEM and the test variables in ‘main’ could be also of help.
On my computer (Ubuntu 16.04.3) this compiled without errors with:
gcc -g -std=c99 -Wall -Wextra -pedantic-errors krmalloc.c
krmalloc.c :
#include #include typedef long Align; /* for alignment to long boundary */ union header { /* block header */ struct { union header *ptr; /* next block if on free list */ size_t size; /* size of this block */ /* including the Header itself */ /* measured in count of Header chunks */ /* not less than NALLOC Header's */ } s; Align x; /* force alignment of blocks */ }; typedef union header Header; static Header *morecore(size_t); void *mmalloc(size_t); void _mfree(void **); void visualize(const char*); size_t getfreem(void); size_t totmem = 0; /* total memory in chunks */ static Header base; /* empty list to get started */ static Header *freep = NULL; /* start of free list */ #define NALLOC 1 /* minimum chunks to request */ #define MAXMEM 2048 /* max memory available (in bytes) */ #define mfree(p) _mfree((void **)&p) void *sbrk(__intptr_t incr); int main(void) { char *pc, *pcc, *pccc, *ps; long *pd, *pdd; int dlen = 100; int ddlen = 50; visualize("start"); /* trying to fragment as much as possible to get a more interesting view */ /* claim a char */ if ((pc = (char *) mmalloc(sizeof(char))) == NULL) return -1; /* claim a string */ if ((ps = (char *) mmalloc(dlen * sizeof(char))) == NULL) return -1; /* claim some long's */ if ((pd = (long *) mmalloc(ddlen * sizeof(long))) == NULL) return -1; /* claim some more long's */ if ((pdd = (long *) mmalloc(ddlen * 2 * sizeof(long))) == NULL) return -1; /* claim one more char */ if ((pcc = (char *) mmalloc(sizeof(char))) == NULL) return -1; /* claim the last char */ if ((pccc = (char *) mmalloc(sizeof(char))) == NULL) return -1; /* free and visualize */ printf("\n"); mfree(pccc); /* bugged on purpose to test free(NULL) */ mfree(pccc); visualize("free(the last char)"); mfree(pdd); visualize("free(lot of long's)"); mfree(ps); visualize("free(string)"); mfree(pd); visualize("free(less long's)"); mfree(pc); visualize("free(first char)"); mfree(pcc); visualize("free(second char)"); /* check memory condition */ size_t freemem = getfreem(); printf("\n"); printf("--- Memory claimed : %ld chunks (%ld bytes)\n", totmem, totmem * sizeof(Header)); printf(" Free memory now : %ld chunks (%ld bytes)\n", freemem, freemem * sizeof(Header)); if (freemem == totmem) printf(" No memory leaks detected.\n"); else printf(" (!) Leaking memory: %ld chunks (%ld bytes).\n", (totmem - freemem), (totmem - freemem) * sizeof(Header)); printf("// Done.\n\n"); return 0; } /* visualize: print the free list (educational purpose) */ void visualize(const char* msg) { Header *tmp; printf("--- Free list after \"%s\":\n", msg); if (freep == NULL) { /* does not exist */ printf("\tList does not exist\n\n"); return; } if (freep == freep->s.ptr) { /* self-pointing list = empty */ printf("\tList is empty\n\n"); return; } printf(" ptr: %10p size: %-3lu --> ", (void *) freep, freep->s.size); tmp = freep; /* find the start of the list */ while (tmp->s.ptr > freep) { /* traverse the list */ tmp = tmp->s.ptr; printf("ptr: %10p size: %-3lu --> ", (void *) tmp, tmp->s.size); } printf("end\n\n"); } /* calculate the total amount of available free memory */ size_t getfreem(void) { if (freep == NULL) return 0; Header *tmp; tmp = freep; size_t res = tmp->s.size; while (tmp->s.ptr > tmp) { tmp = tmp->s.ptr; res += tmp->s.size; } return res; } /* mmalloc: general-purpose storage allocator */ void *mmalloc(size_t nbytes) { Header *p, *prevp; size_t nunits; /* smallest count of Header-sized memory chunks */ /* (+1 additional chunk for the Header itself) needed to hold nbytes */ nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1; /* too much memory requested? */ if (((nunits + totmem + getfreem())*sizeof(Header)) > MAXMEM) { printf("Memory limit overflow!\n"); return NULL; } if ((prevp = freep) == NULL) { /* no free list yet */ /* set the list to point to itself */ base.s.ptr = freep = prevp = &base; base.s.size = 0; } /* traverse the circular list */ for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) { if (p->s.size >= nunits) { /* big enough */ if (p->s.size == nunits) /* exactly */ prevp->s.ptr = p->s.ptr; else { /* allocate tail end */ /* adjust the size */ p->s.size -= nunits; /* find the address to return */ p += p->s.size; p->s.size = nunits; } freep = prevp; return (void *)(p+1); } /* back where we started and nothing found - we need to allocate */ if (p == freep) /* wrapped around free list */ if ((p = morecore(nunits)) == NULL) return NULL; /* none left */ } } /* morecore: ask system for more memory */ /* nu: count of Header-chunks needed */ static Header *morecore(size_t nu) { char *cp; Header *up; /* get at least NALLOC Header-chunks from the OS */ if (nu < NALLOC) nu = NALLOC; cp = (char *) sbrk(nu * sizeof(Header)); if (cp == (char *) -1) /* no space at all */ return NULL; printf("... (sbrk) claimed %ld chunks.\n", nu); totmem += nu; /* keep track of allocated memory */ up = (Header *) cp; up->s.size = nu; /* add the free space to the circular list */ void *n = (void *)(up+1); mfree(n); return freep; } /* mfree: put block ap in free list */ void _mfree(void **ap) { if (*ap == NULL) return; Header *bp, *p; bp = (Header *)*ap - 1; /* point to block header */ if (bp->s.size == 0 || bp->s.size > totmem) { printf("_mfree: impossible value for size\n"); return; } /* the free space is only marked as free, but 'ap' still points to it */ /* to avoid reusing this address and corrupt our structure set it to '\0' */ *ap = NULL; /* look where to insert the free space */ /* (bp > p && bp < p->s.ptr) => between two nodes */ /* (p > p->s.ptr) => this is the end of the list */ /* (p == p->p.str) => list is one element only */ for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr) if (p >= p->s.ptr && (bp > p || bp < p->s.ptr)) /* freed block at start or end of arena */ break; if (bp + bp->s.size == p->s.ptr) { /* join to upper nbr */ /* the new block fits perfect up to the upper neighbor */ /* merging up: adjust the size */ bp->s.size += p->s.ptr->s.size; /* merging up: point to the second next */ bp->s.ptr = p->s.ptr->s.ptr; } else /* set the upper pointer */ bp->s.ptr = p->s.ptr; if (p + p->s.size == bp) { /* join to lower nbr */ /* the new block fits perfect on top of the lower neighbor */ /* merging below: adjust the size */ p->s.size += bp->s.size; /* merging below: point to the next */ p->s.ptr = bp->s.ptr; } else /* set the lower pointer */ p->s.ptr = bp; /* reset the start of the free list */ freep = p; }