/*
* 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.
*/

/*
* malloc.c - Linux ͨںڴ亯
*
* Theodore Ts'o  (tytso@mit.edu), 11/29/91
*
* úдɾܵؿ죬ӶԴжϲô˺
*
* ƣʹøúһܷڴ4kҲLinux ڴҳĴС
*
* дúѭһÿҳ(Ϊһ洢Ͱ)ҪɶĴС
* һҳϵжͷź󣬸ҳͿԷͨÿڴءmalloc()
* ʱѰҪСĴ洢ͰӸô洢Ͱзһڴ档
*
* ÿ洢ͰһΪõĴ洢Ͱм¼ҳжٶ
* ʹԼҳϿڴб洢Ͱһ洢ͰҲǴ洢ʹ
* get_free_page()뵽ҳϵģ洢ͰͬǣͰռõҳ
* ٻͷŸϵͳ˵һϵͳԼֻҪ1 2 ҳͰҳ棬Ϊһ
* ҳԴ256 Ͱ(Ӧ1MB ڴĴ洢Ͱҳ)ϵͳΪͰ

* ڴ棬ô϶ϵͳʲôط?
*
* ע⣡malloc()free()߹رжϵĴ벿ֶget_free_page()
* free_page()ʹmalloc()free()԰ȫرжϳе
* (룬NFS ȱ뵽Linux ʱͿҪֹ)ǰ
* Ǽget_free_page()free_page()ǿ԰ȫжϼʹõģ
* һ˷ҳ֮Ϳܲǰȫġô
* Ҫ޸malloc()Ԥȷ䡱ҳõڴ棬malloc()free()
* жϳеʱͿ԰ȫʹЩҳ档
*
* Ҫǵget_free_page()Ӧ˯ߣ˯ߵĻΪ˷ֹ
* κξҪϸذ˳ ؼmalloc()ǿ
* õĻôͻڲҪҳ汻ϵͳȡߵĻᡣͰ
* ҳ棬ЩҳջͷŸϵͳԲá
*/
#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.
*/
/*
* ǴŵһС洢Ͱָĵط
*
* Linux ں˷ָСĶôǾϣָĴСӵ
* б()УΪʹڴķЧǣΪһҳڴҳ
* бָСжҪĲԲ

*/
// 洢ͰĿ¼б()
struct _bucket_dir bucket_dir[] = {
  {16, (struct bucket_desc *) 0},	// 16 ֽڳȵڴ顣
  {32, (struct bucket_desc *) 0},	// 32 ֽڳȵڴ顣
  {64, (struct bucket_desc *) 0},	// 64 ֽڳȵڴ顣
  {128, (struct bucket_desc *) 0},	// 128 ֽڳȵڴ顣
  {256, (struct bucket_desc *) 0},	// 256 ֽڳȵڴ顣
  {512, (struct bucket_desc *) 0},	// 512 ֽڳȵڴ顣
  {1024, (struct bucket_desc *) 0},	// 1024 ֽڳȵڴ顣
  {2048, (struct bucket_desc *) 0},	// 2048 ֽڳȵڴ顣
  {4096, (struct bucket_desc *) 0},	// 4096 ֽ(1 ҳ)ڴ档
  {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.
*/
/*
* ӳڳʼһҳͰҳ档
*/
//// ʼͰ
// Ͱfree_bucket_desc ָһͰ
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....
*/
/*
* ģĿΪ˱get_free_page()˯ʱӳֱ
* öľ
*/
// Ͱָfree_bucket_desc С

  bdesc->next = free_bucket_desc;
  free_bucket_desc = first;
}

//// 䶯̬ڴ溯
// len - ڴ鳤ȡ
// أָ򱻷ڴָ롣ʧ򷵻NULL
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.
*/
/*
* 洢ͰĿ¼bucket_dir ѰʺͰС
*/
// 洢ͰĿ¼ѰʺڴСͰĿ¼Ͱֽֽ
// ҵ˶ӦͰĿ¼
  for (bdir = bucket_dir; bdir->size; bdir++)
    if (bdir->size >= len)
      break;
// Ŀ¼ûҵʴСĿ¼ڴС̫󣬳˸
// ķ(Ϊ1 ҳ)ʾϢ
  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 *//* Ϊ˱־ȹж */
// ӦͰĿ¼ҾппռͰͰĿڴָ
// freeptr ΪգʾҵӦͰ
  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;

// free_bucket_desc Ϊʱʾһεøóгʼ
// free_bucket_desc ָһͰ
      if (!free_bucket_desc)
	init_bucket_desc ();
// ȡfree_bucket_desc ָĿͰfree_bucket_desc ָһͰ
      bdesc = free_bucket_desc;
      free_bucket_desc = bdesc->next;
// ʼµͰ0ͰĴСڶӦͰĿ¼ĴСһڴҳ棬
// ҳָpage ָҳ棻ڴָҲָҳͷΪʱȫΪС
      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 */
/* ڸҳڴнж */
// ԸͰĿ¼ָͰСΪ󳤶ȣԸҳڴл֣ʹÿĿʼ4 ֽ
// ָһָ롣
      for (i = PAGE_SIZE / bdir->size; i > 1; i--)
	{
	  *((char **) cp) = cp + bdir->size;
	  cp += bdir->size;
	}
// һʼָΪ0(NULL)
// ȻøͰһֶָָӦͰĿ¼ָchain ָͰĿ¼
// chain ָͰҲ뵽ͷ
      *((char **) cp) = 0;
      bdesc->next = bdir->chain;	/* OK, link it in! *//* OK룡 */
      bdir->chain = bdesc;
    }
// ָ뼴ڸӦҳĵǰָ롣Ȼÿпռָָһж
// ʹжӦҳжü1
  retval = (void *) bdesc->freeptr;
  bdesc->freeptr = *((void **) retval);
  bdesc->refcnt++;
// 󿪷жϣָڴָ롣
  sti ();			/* OK, we're safe again *//* OKְȫ */
  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)"
*/
/*
* ͷӳ֪ͷŶĴСfree_s()ʹøϢ
* ѰӦͰٶȡ
*

* ǽһ꣬ʹ"free(x)"Ϊ"free_s(x, 0)"
*/
//// ͷŴ洢Ͱ
// obj - Ӧָ룻size - С
void
free_s (void *obj, int size)
{
  void *page;
  struct _bucket_dir *bdir;
  struct bucket_desc *bdesc, *prev;

/* 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 */
/* size 0϶false */
      if (bdir->size < size)
	continue;
// ӦĿ¼ӵҶӦҳ档ĳҳָpage ʾҵ
// ӦתfoundжӦpageָprev ָ
      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:
// ҵӦͰȹжϡȻ󽫸öڴпУʹ
// Ķü1
  cli ();			/* To avoid race conditions *//* Ϊ˱⾺ */
  *((void **) obj) = bdesc->freeptr;
  bdesc->freeptr = obj;
  bdesc->refcnt--;
// üѵ0ǾͿͷŶӦڴҳ͸Ͱ
  if (bdesc->refcnt == 0)
    {
/*
* We need to make sure that prev is still accurate. It
* may not be, if someone rudely interrupted us....
*/
/*
* Ҫȷprev Ȼȷģĳ³ж
* пܲˡ
*/
// prev Ѿǰһǰǰһ
      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;
// prev==NULL˵ǰһǸĿ¼׸ҲĿ¼chain Ӧֱ
// ָǰbdescʾ⣬ʾϢˣΪ˽ǰ
// ɾӦchain ָһ
      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;
}
