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