Introduction to malloc
The `malloc.c` file in Linux kernel version 0.11 implements the memory allocation function. In this version of the Linux kernel, the `malloc.c` file contains kernel-level memory allocation functions for allocating and freeing memory in the kernel. These functions help the kernel manage available memory and allow the kernel to dynamically allocate and free memory to meet the memory needs of different modules or processes at runtime. Basically, it implements functionality similar to the `malloc()` and `free()` functions in the C standard library, but is designed for kernel-level operations.
The difference between malloc in the C standard library and the kernel
In order to distinguish them, malloc is named kmalloc and free is named kfree.
There are some key differences between the `malloc` function in the C standard library and the `malloc` function in the kernel:
1. **Different scopes**: The `malloc` function in the C standard library is used for memory allocation of user space programs, while the `malloc` function in the kernel is used for memory management of the operating system kernel.
2. **Different permissions**: The `malloc` function in the C standard library can only operate the memory in user space, while the `malloc` function in the kernel can directly operate the operating system’s memory, including the memory in the kernel space.
3. **Different implementations**: The `malloc` function in the C standard library is usually implemented based on the heap in user space, while the `malloc` function in the kernel is implemented based on the memory management mechanism of kernel space, so it is more low-level and complex. .
4. **Different uses**: The `malloc` function in the C standard library is mainly used for dynamic memory allocation of user space programs, while the `malloc` function in the kernel is used for dynamic memory allocation of the operating system kernel, including kernel data. Allocation of structures and buffers.
Bucket allocation algorithm
The Bucket memory allocation algorithm is a method for managing dynamic memory allocation, usually applied to user space memory allocation libraries. This algorithm is based on fixed-size memory blocks (or buckets), each of which is the same size and is determined in advance. These buckets can be memory blocks of different sizes to accommodate different size memory requirements.
The basic idea is to divide the memory space into buckets (or blocks) of predefined sizes, such as 8 bytes, 16 bytes, 32 bytes, etc. When a program requests to allocate a certain size of memory, the allocator will find a bucket of the appropriate size based on the requested size, and then allocate memory from this bucket. If memory of sufficient size is not available in a bucket, it attempts to split appropriately sized blocks of memory from a larger bucket to satisfy the request.
The advantages of this algorithm are:
1. **Reduce memory fragmentation**: By using buckets of predefined sizes, memory fragmentation can be reduced, because the size of each bucket is fixed and there will be no scattered small memory fragments.
2. **Fast Allocation**: Since multiple fixed-size buckets are predefined, the allocator only needs to find the corresponding bucket according to the request size, so the allocation speed is relatively fast.
However, the Bucket memory allocation algorithm also has some limitations:
1. **Memory waste**: When the required memory size does not exactly match the bucket size, it may cause a certain degree of memory waste.
2. **Fixed bucket size**: Since each bucket size is fixed, it may be difficult to adapt to the memory requirements of a specific size.
Structure introduction
`struct bucket_desc` represents a bucket descriptor and contains the following fields:
– `void *page`: points to the starting address of the bucket.
– `struct bucket_desc *next`: Points to the descriptor of the next bucket, used to build a linked list.
– `void *freeptr`: Points to the starting address of free memory in the bucket.
– `unsigned short refcnt`: Reference counting, used to track bucket usage.
– `unsigned short bucket_size`: The size of the bucket, indicating the size of the memory block that can be allocated to each bucket.
`struct _bucket_dir` represents the bucket directory and contains the following fields:
– `int size`: The directory size of the bucket, indicating the number of buckets.
– `struct bucket_desc *chain`: Points to the head of the bucket list, used to manage the allocation of all buckets.
These structures are designed to implement the core functions of the Bucket memory allocation algorithm. The usage of each bucket can be tracked and managed through the linked list and reference counting in `struct bucket_desc`. The linked list header and directory size in `struct _bucket_dir` can help locate and manage the allocation of all buckets.
struct bucket_desc { /* 16 bytes */
void *page;
struct bucket_desc *next;
void *freeptr;
unsigned short refcnt;
unsigned short bucket_size;
};
struct _bucket_dir { /* 8 bytes */
int size;
struct bucket_desc *chain;
};
struct _bucket_dir bucket_dir[] = {
{ 16, (struct bucket_desc *) 0},
{ 32, (struct bucket_desc *) 0},
{ 64, (struct bucket_desc *) 0},
{ 128, (struct bucket_desc *) 0},
{ 256, (struct bucket_desc *) 0},
{ 512, (struct bucket_desc *) 0},
{ 1024, (struct bucket_desc *) 0},
{ 2048, (struct bucket_desc *) 0},
{ 4096, (struct bucket_desc *) 0},
{ 0, (struct bucket_desc *) 0}}; /* End of list marker */
/*
* This contains a linked list of free bucket descriptor blocks
*/
struct bucket_desc *free_bucket_desc = (struct bucket_desc *) 0;
free bucket
Bucket structure initialization
Initialize the bucket descriptor and establish a free bucket descriptor list
/*
* This routine initializes a bucket description page.
*/
static inline void init_bucket_desc()
{
struct bucket_desc *bdesc, *first;
int i;
Apply for one page of memory
first = bdesc = (struct bucket_desc *) get_free_page();
if (!bdesc)
panic("Out of memory in init_bucket_desc()");
Calculate the number of bucket descriptors that can be stored in one page of memory
for (i = PAGE_SIZE/sizeof(struct bucket_desc); i > 1; i--) {
bdesc->next = bdesc + 1;
bdesc + + ;
}
/*
* This is done last, to avoid race conditions in case
* get_free_page() sleeps and this routine gets called again....
*/
Add the free bucket description pointer to the linked list
bdesc->next = free_bucket_desc;
free_bucket_desc = first;
}
malloc function
Allocate dynamic memory function
void *malloc(unsigned int len)
{
struct _bucket_dir *bdir;
struct bucket_desc *bdesc;
void *retval;
/*
* First we search the bucket_dir to find the right bucket change
* for this request.
*/
Find the right bucket
for (bdir = bucket_dir; bdir->size; bdir + + )
if (bdir->size >= len)
break;
if (!bdir->size) {
printk("malloc called with impossibly large argument (%d)\
",
len);
panic("malloc: bad arg");
}
/*
* Now we search for a bucket descriptor which has free space
*/
cli(); /* Avoid race conditions */
Find the bucket descriptor of the corresponding bucket free space
for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next)
if (bdesc->freeptr)
break;
/*
* If we didn't find a bucket with free space, then we'll
* allocate a new one.
*/
if (!bdesc) {
char *cp;
int i;
if (!free_bucket_desc)
init_bucket_desc();
bdesc = free_bucket_desc;
free_bucket_desc = bdesc->next;
bdesc->refcnt = 0;
bdesc->bucket_size = bdir->size;
bdesc->page = bdesc->freeptr = (void *) (cp = get_free_page());
if (!cp)
panic("Out of memory in kernel malloc()");
/* Set up the chain of free objects */
for (i=PAGE_SIZE/bdir->size; i > 1; i--) {
*((char **) cp) = cp + bdir->size;
cp + = bdir->size;
}
*((char **) cp) = 0;
bdesc->next = bdir->chain; /* OK, link it in! */
bdir->chain = bdesc;
}
The return pointer is equal to the current free pointer of the page corresponding to the descriptor.
retval = (void *) bdesc->freeptr;
Adjust the free pointer to point to the next object
bdesc->freeptr = *((void **) retval);
Quote + 1
bdesc->refcnt + + ;
development interruption
sti(); /* OK, we're safe again */
return(retval);
}
free releases memory
/*
* Here is the free routine. If you know the size of the object that you
* are freeing, then free_s() will use that information to speed up the
* search for the bucket descriptor.
*
* We will #define a macro so that "free(x)" is becomes "free_s(x, 0)"
*/
void free_s(void *obj, int size)
{
void *page;
struct _bucket_dir *bdir;
struct bucket_desc *bdesc, *prev;
bdesc = prev = 0;
/* Calculate what page this object lives in */
page = (void *) ((unsigned long) obj & amp; 0xfffff000);
/* Now search the buckets looking for that page */
for (bdir = bucket_dir; bdir->size; bdir + + ) {
prev = 0;
/* If size is zero then this conditional is always false */
if (bdir->size < size)
continue;
for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next) {
if (bdesc->page == page)
goto found;
prev = bdesc;
}
}
panic("Bad address passed to kernel free_s()");
found:
cli(); /* To avoid race conditions */
*((void **)obj) = bdesc->freeptr;
bdesc->freeptr = obj;
bdesc->refcnt--;
if (bdesc->refcnt == 0) {
/*
* We need to make sure that prev is still accurate. It
* may not be, if someone rudely interrupted us....
*/
if ((prev & amp; & amp; (prev->next != bdesc)) ||
(!prev & amp; & amp; (bdir->chain != bdesc)))
for (prev = bdir->chain; prev; prev = prev->next)
if (prev->next == bdesc)
break;
if (prev)
prev->next = bdesc->next;
else {
if (bdir->chain != bdesc)
panic("malloc bucket chains corrupted");
bdir->chain = bdesc->next;
}
free_page((unsigned long) bdesc->page);
bdesc->next = free_bucket_desc;
free_bucket_desc = bdesc;
}
sti();
return;
}