1 files changed, 232 insertions, 0 deletions
diff --git a/src/lib/malloc.c b/src/lib/malloc.c
new file mode 100644
index 0000000..ef7abf3
--- /dev/null
+++ b/src/lib/malloc.c
@@ -0,0 +1,232 @@
+/*
+ * malloc.c --- a general purpose kernel memory allocator for Linux.
+ * 
+ * Written by Theodore Ts'o (tytso@mit.edu), 11/29/91
+ *
+ * This routine is written to be as fast as possible, so that it
+ * can be called from the interrupt level.
+ *
+ * Limitations: maximum size of memory we can allocate using this routine
+ *      is 4k, the size of a page in Linux.
+ *
+ * The general game plan is that each page (called a bucket) will only hold
+ * objects of a given size.  When all of the object on a page are released,
+ * the page can be returned to the general free pool.  When malloc() is
+ * called, it looks for the smallest bucket size which will fulfill its
+ * request, and allocate a piece of memory from that bucket pool.
+ *
+ * Each bucket has as its control block a bucket descriptor which keeps 
+ * track of how many objects are in use on that page, and the free list
+ * for that page.  Like the buckets themselves, bucket descriptors are
+ * stored on pages requested from get_free_page().  However, unlike buckets,
+ * pages devoted to bucket descriptor pages are never released back to the
+ * system.  Fortunately, a system should probably only need 1 or 2 bucket
+ * descriptor pages, since a page can hold 256 bucket descriptors (which
+ * corresponds to 1 megabyte worth of bucket pages.)  If the kernel is using 
+ * that much allocated memory, it's probably doing something wrong.  :-)
+ *
+ * Note: malloc() and free() both call get_free_page() and free_page()
+ *      in sections of code where interrupts are turned off, to allow
+ *      malloc() and free() to be safely called from an interrupt routine.
+ *      (We will probably need this functionality when networking code,
+ *      particularily things like NFS, is added to Linux.)  However, this
+ *      presumes that get_free_page() and free_page() are interrupt-level
+ *      safe, which they may not be once paging is added.  If this is the
+ *      case, we will need to modify malloc() to keep a few unused pages
+ *      "pre-allocated" so that it can safely draw upon those pages if
+ *      it is called from an interrupt routine.
+ *
+ *      Another concern is that get_free_page() should not sleep; if it 
+ *      does, the code is carefully ordered so as to avoid any race 
+ *      conditions.  The catch is that if malloc() is called re-entrantly, 
+ *      there is a chance that unecessary pages will be grabbed from the 
+ *      system.  Except for the pages for the bucket descriptor page, the 
+ *      extra pages will eventually get released back to the system, though,
+ *      so it isn't all that bad.
+ */
+#include <linux/kernel.h>
+#include <linux/mm.h>
+#include <asm/system.h>
+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;
+};
+/*
+ * The following is the where we store a pointer to the first bucket
+ * descriptor for a given size.  
+ *
+ * If it turns out that the Linux kernel allocates a lot of objects of a
+ * specific size, then we may want to add that specific size to this list,
+ * since that will allow the memory to be allocated more efficiently.
+ * However, since an entire page must be dedicated to each specific size
+ * on this list, some amount of temperance must be exercised here.
+ *
+ * Note that this list *must* be kept in order.
+ */
+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;
+/*
+ * This routine initializes a bucket description page.
+ */
+static inline void init_bucket_desc()
+{
+        struct bucket_desc *bdesc, *first;
+        int     i;
+        
+        first = bdesc = (struct bucket_desc *) get_free_page();
+        if (!bdesc)
+                panic("Out of memory in init_bucket_desc()");
+        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....
+         */
+        bdesc->next = free_bucket_desc;
+        free_bucket_desc = first;
+}
+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.
+         */
+        for (bdir = bucket_dir; bdir->size; bdir++)
+                if (bdir->size >= len)
+                        break;
+        if (!bdir->size) {
+                printk("malloc called with impossibly large argument (%d)\n",
+                        len);
+                panic("malloc: bad arg");
+        }
+        /*
+         * Now we search for a bucket descriptor which has free space
+         */
+        cli();  /* Avoid race conditions */
+        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 = (char *) 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;
+        }
+        retval = (void *) bdesc->freeptr;
+        bdesc->freeptr = *((void **) retval);
+        bdesc->refcnt++;
+        sti();  /* OK, we're safe again */
+        return(retval);
+}
+/*
+ * 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 & 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 && (prev->next != bdesc)) ||
+                    (!prev && (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;
+}

diff --git a/src/lib/malloc.c b/src/lib/malloc.c new file mode 100644 index 0000000..ef7abf3 --- /dev/null +++ b/src/lib/malloc.c
@@ -0,0 +1,232 @@
	1	/*
	2	* malloc.c --- a general purpose kernel memory allocator for Linux.
	3	*
	4	* Written by Theodore Ts'o (tytso@mit.edu), 11/29/91
	5	*
	6	* This routine is written to be as fast as possible, so that it
	7	* can be called from the interrupt level.
	8	*
	9	* Limitations: maximum size of memory we can allocate using this routine
	10	* is 4k, the size of a page in Linux.
	11	*
	12	* The general game plan is that each page (called a bucket) will only hold
	13	* objects of a given size. When all of the object on a page are released,
	14	* the page can be returned to the general free pool. When malloc() is
	15	* called, it looks for the smallest bucket size which will fulfill its
	16	* request, and allocate a piece of memory from that bucket pool.
	17	*
	18	* Each bucket has as its control block a bucket descriptor which keeps
	19	* track of how many objects are in use on that page, and the free list
	20	* for that page. Like the buckets themselves, bucket descriptors are
	21	* stored on pages requested from get_free_page(). However, unlike buckets,
	22	* pages devoted to bucket descriptor pages are never released back to the
	23	* system. Fortunately, a system should probably only need 1 or 2 bucket
	24	* descriptor pages, since a page can hold 256 bucket descriptors (which
	25	* corresponds to 1 megabyte worth of bucket pages.) If the kernel is using
	26	* that much allocated memory, it's probably doing something wrong. :-)
	27	*
	28	* Note: malloc() and free() both call get_free_page() and free_page()
	29	* in sections of code where interrupts are turned off, to allow
	30	* malloc() and free() to be safely called from an interrupt routine.
	31	* (We will probably need this functionality when networking code,
	32	* particularily things like NFS, is added to Linux.) However, this
	33	* presumes that get_free_page() and free_page() are interrupt-level
	34	* safe, which they may not be once paging is added. If this is the
	35	* case, we will need to modify malloc() to keep a few unused pages
	36	* "pre-allocated" so that it can safely draw upon those pages if
	37	* it is called from an interrupt routine.
	38	*
	39	* Another concern is that get_free_page() should not sleep; if it
	40	* does, the code is carefully ordered so as to avoid any race
	41	* conditions. The catch is that if malloc() is called re-entrantly,
	42	* there is a chance that unecessary pages will be grabbed from the
	43	* system. Except for the pages for the bucket descriptor page, the
	44	* extra pages will eventually get released back to the system, though,
	45	* so it isn't all that bad.
	46	*/
	47
	48	#include <linux/kernel.h>
	49	#include <linux/mm.h>
	50	#include <asm/system.h>
	51
	52	struct bucket_desc { /* 16 bytes */
	53	void *page;
	54	struct bucket_desc *next;
	55	void *freeptr;
	56	unsigned short refcnt;
	57	unsigned short bucket_size;
	58	};
	59
	60	struct _bucket_dir { /* 8 bytes */
	61	int size;
	62	struct bucket_desc *chain;
	63	};
	64
	65	/*
	66	* The following is the where we store a pointer to the first bucket
	67	* descriptor for a given size.
	68	*
	69	* If it turns out that the Linux kernel allocates a lot of objects of a
	70	* specific size, then we may want to add that specific size to this list,
	71	* since that will allow the memory to be allocated more efficiently.
	72	* However, since an entire page must be dedicated to each specific size
	73	* on this list, some amount of temperance must be exercised here.
	74	*
	75	* Note that this list must be kept in order.
	76	*/
	77	struct _bucket_dir bucket_dir[] = {
	78	{ 16, (struct bucket_desc *) 0},
	79	{ 32, (struct bucket_desc *) 0},
	80	{ 64, (struct bucket_desc *) 0},
	81	{ 128, (struct bucket_desc *) 0},
	82	{ 256, (struct bucket_desc *) 0},
	83	{ 512, (struct bucket_desc *) 0},
	84	{ 1024, (struct bucket_desc *) 0},
	85	{ 2048, (struct bucket_desc *) 0},
	86	{ 4096, (struct bucket_desc *) 0},
	87	{ 0, (struct bucket_desc ) 0}}; / End of list marker */
	88
	89	/*
	90	* This contains a linked list of free bucket descriptor blocks
	91	*/
	92	struct bucket_desc free_bucket_desc = (struct bucket_desc ) 0;
	93
	94	/*
	95	* This routine initializes a bucket description page.
	96	*/
	97	static inline void init_bucket_desc()
	98	{
	99	struct bucket_desc bdesc, first;
	100	int i;
	101
	102	first = bdesc = (struct bucket_desc *) get_free_page();
	103	if (!bdesc)
	104	panic("Out of memory in init_bucket_desc()");
	105	for (i = PAGE_SIZE/sizeof(struct bucket_desc); i > 1; i--) {
	106	bdesc->next = bdesc+1;
	107	bdesc++;
	108	}
	109	/*
	110	* This is done last, to avoid race conditions in case
	111	* get_free_page() sleeps and this routine gets called again....
	112	*/
	113	bdesc->next = free_bucket_desc;
	114	free_bucket_desc = first;
	115	}
	116
	117	void *malloc(unsigned int len)
	118	{
	119	struct _bucket_dir *bdir;
	120	struct bucket_desc *bdesc;
	121	void *retval;
	122
	123	/*
	124	* First we search the bucket_dir to find the right bucket change
	125	* for this request.
	126	*/
	127	for (bdir = bucket_dir; bdir->size; bdir++)
	128	if (bdir->size >= len)
	129	break;
	130	if (!bdir->size) {
	131	printk("malloc called with impossibly large argument (%d)\n",
	132	len);
	133	panic("malloc: bad arg");
	134	}
	135	/*
	136	* Now we search for a bucket descriptor which has free space
	137	*/
	138	cli(); /* Avoid race conditions */
	139	for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next)
	140	if (bdesc->freeptr)
	141	break;
	142	/*
	143	* If we didn't find a bucket with free space, then we'll
	144	* allocate a new one.
	145	*/
	146	if (!bdesc) {
	147	char *cp;
	148	int i;
	149
	150	if (!free_bucket_desc)
	151	init_bucket_desc();
	152	bdesc = free_bucket_desc;
	153	free_bucket_desc = bdesc->next;
	154	bdesc->refcnt = 0;
	155	bdesc->bucket_size = bdir->size;
	156	bdesc->page = bdesc->freeptr = (void ) (cp = (char ) get_free_page());
	157	if (!cp)
	158	panic("Out of memory in kernel malloc()");
	159	/* Set up the chain of free objects */
	160	for (i=PAGE_SIZE/bdir->size; i > 1; i--) {
	161	((char *) cp) = cp + bdir->size;
	162	cp += bdir->size;
	163	}
	164	((char *) cp) = 0;
	165	bdesc->next = bdir->chain; /* OK, link it in! */
	166	bdir->chain = bdesc;
	167	}
	168	retval = (void *) bdesc->freeptr;
	169	bdesc->freeptr = ((void *) retval);
	170	bdesc->refcnt++;
	171	sti(); /* OK, we're safe again */
	172	return(retval);
	173	}
	174
	175	/*
	176	* Here is the free routine. If you know the size of the object that you
	177	* are freeing, then free_s() will use that information to speed up the
	178	* search for the bucket descriptor.
	179	*
	180	* We will #define a macro so that "free(x)" is becomes "free_s(x, 0)"
	181	*/
	182	void free_s(void *obj, int size)
	183	{
	184	void *page;
	185	struct _bucket_dir *bdir;
	186	struct bucket_desc bdesc, prev;
	187	bdesc = prev = 0;
	188	/* Calculate what page this object lives in */
	189	page = (void *) ((unsigned long) obj & 0xfffff000);
	190	/* Now search the buckets looking for that page */
	191	for (bdir = bucket_dir; bdir->size; bdir++) {
	192	prev = 0;
	193	/* If size is zero then this conditional is always false */
	194	if (bdir->size < size)
	195	continue;
	196	for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next) {
	197	if (bdesc->page == page)
	198	goto found;
	199	prev = bdesc;
	200	}
	201	}
	202	panic("Bad address passed to kernel free_s()");
	203	found:
	204	cli(); /* To avoid race conditions */
	205	((void *)obj) = bdesc->freeptr;
	206	bdesc->freeptr = obj;
	207	bdesc->refcnt--;
	208	if (bdesc->refcnt == 0) {
	209	/*
	210	* We need to make sure that prev is still accurate. It
	211	* may not be, if someone rudely interrupted us....
	212	*/
	213	if ((prev && (prev->next != bdesc)) \|\|
	214	(!prev && (bdir->chain != bdesc)))
	215	for (prev = bdir->chain; prev; prev = prev->next)
	216	if (prev->next == bdesc)
	217	break;
	218	if (prev)
	219	prev->next = bdesc->next;
	220	else {
	221	if (bdir->chain != bdesc)
	222	panic("malloc bucket chains corrupted");
	223	bdir->chain = bdesc->next;
	224	}
	225	free_page((unsigned long) bdesc->page);
	226	bdesc->next = free_bucket_desc;
	227	free_bucket_desc = bdesc;
	228	}
	229	sti();
	230	return;
	231	}
	232