malloc.c ( File view )

  • By 2010-08-31
  • View(s):24
  • Download(s):2
  • Point(s): 1
			/*
* 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 *//* 为了避免出现竞争条件,首先关中断 */
// 搜索对应桶目录项中描述符链表,查找具有空闲空间的桶描述符。如果桶描述符的空闲内存指
...
...
(Not finished, please download and read the complete file)
			
...
Expand> <Close

Want complete source code? Download it here

Point(s): 1

Download
0 lines left, continue to read
Sponsored links

File list

Tips: You can preview the content of files by clicking file names^_^
Name Size Date
linux0.00 B0% 04-10-07
<boot>0.00 B04-10-07 15:01
bootsect.s12.49 kB08-01-04 21:38
head.s13.22 kB08-01-04 21:38
setup.s12.42 kB08-01-04 21:38
<fs>0.00 B04-10-07 15:01
bitmap.c8.46 kB02-09-04 13:12
block_dev.c3.95 kB02-09-04 13:12
buffer.c17.71 kB02-09-04 13:12
char_dev.c4.09 kB02-09-04 13:12
exec.c18.90 kB02-09-04 13:12
fcntl.c3.33 kB02-09-04 13:12
file_dev.c4.82 kB02-09-04 13:12
file_table.c209.00 B02-09-04 13:12
inode.c14.92 kB02-09-04 13:12
ioctl.c1.94 kB02-09-04 13:12
Makefile6.80 kB08-01-04 21:45
namei.c37.20 kB02-09-04 13:12
open.c10.00 kB02-09-04 13:12
pipe.c5.42 kB02-09-04 13:12
read_write.c5.86 kB02-09-04 13:12
stat.c2.69 kB02-09-04 13:12
super.c13.57 kB02-09-04 13:12
truncate.c2.46 kB02-09-04 13:12
<include>0.00 B04-10-07 15:01
a.out.h8.22 kB02-09-04 13:14
<asm>0.00 B04-10-07 15:01
io.h772.00 B02-09-04 13:14
memory.h1.03 kB08-01-04 22:13
segment.h2.50 kB02-09-04 13:14
system.h4.08 kB02-09-04 13:14
const.h589.00 B02-09-04 13:14
ctype.h1.68 kB02-09-04 13:14
errno.h2.30 kB02-09-04 13:14
fcntl.h3.30 kB02-09-04 13:14
<linux>0.00 B04-10-07 15:01
config.h2.16 kB02-09-04 13:14
fs.h9.72 kB02-09-04 13:14
hdreg.h2.94 kB02-09-04 13:14
head.h760.00 B02-09-04 13:14
kernel.h1.44 kB02-09-04 13:14
mm.h473.00 B02-09-04 13:14
sched.h13.25 kB02-09-04 13:14
sys.h5.41 kB02-09-04 13:14
tty.h3.93 kB02-09-04 13:14
signal.h4.01 kB02-09-04 13:14
stdarg.h1.77 kB02-09-04 13:14
stddef.h378.00 B02-09-04 13:14
string.h21.75 kB02-09-04 13:14
<sys>0.00 B04-10-07 15:01
stat.h2.37 kB02-09-04 13:14
times.h377.00 B02-09-04 13:14
types.h1.10 kB02-09-04 13:14
utsname.h423.00 B02-09-04 13:14
wait.h1.48 kB02-09-04 13:14
termios.h13.58 kB02-09-04 13:14
time.h1.81 kB02-09-04 13:14
unistd.h9.21 kB02-09-04 13:14
utime.h392.00 B02-09-04 13:14
<init>0.00 B04-10-07 15:01
main.c12.52 kB02-09-04 13:12
<kernel>0.00 B04-10-07 15:01
asm.s5.10 kB08-01-04 22:48
<blk_drv>0.00 B04-10-07 15:01
blk.h5.69 kB02-09-04 13:14
floppy.c23.49 kB02-09-04 13:12
hd.c17.14 kB02-09-04 13:12
ll_rw_blk.c7.59 kB02-09-04 13:12
Makefile4.25 kB08-01-04 22:53
ramdisk.c6.13 kB02-09-04 13:12
<chr_drv>0.00 B04-10-07 15:01
console.c30.91 kB02-09-04 13:12
keyboard.S21.04 kB08-01-04 22:59
Makefile4.81 kB08-01-04 22:59
rs_io.s5.75 kB08-01-04 22:59
serial.c2.91 kB02-09-04 13:12
tty_io.c18.40 kB02-09-04 13:12
tty_ioctl.c10.70 kB02-09-04 13:12
exit.c8.08 kB02-09-04 13:12
fork.c6.78 kB15-07-07 22:10
<math>0.00 B04-10-07 15:01
Makefile3.21 kB08-01-04 23:01
math_emulate.c2.08 kB02-09-04 13:12
mktime.c2.72 kB02-09-04 13:12
panic.c952.00 B02-09-04 13:12
printk.c1.75 kB02-09-04 13:12
sched.c18.57 kB16-07-07 21:23
signal.c5.61 kB02-09-04 13:12
sys.c7.62 kB02-09-04 13:12
system_call.s12.53 kB08-01-04 22:48
traps.c8.29 kB04-10-07 14:57
vsprintf.c9.96 kB02-09-04 13:12
<lib>0.00 B04-10-07 15:01
close.c397.00 B02-09-04 13:12
ctype.c1.72 kB02-09-04 13:12
dup.c401.00 B02-09-04 13:12
errno.c66.00 B02-09-04 13:12
execve.c607.00 B02-09-04 13:12
Makefile4.83 kB08-01-04 22:30
malloc.c13.50 kB02-09-04 13:12
open.c1.22 kB02-09-04 13:12
setsid.c382.00 B02-09-04 13:12
string.c199.00 B02-09-04 13:12
wait.c774.00 B02-09-04 13:12
write.c545.00 B02-09-04 13:12
_exit.c616.00 B02-09-04 13:12
Makefile8.58 kB08-01-04 22:21
<mm>0.00 B04-10-07 15:01
Makefile2.91 kB08-01-04 22:34
memory.c25.10 kB02-09-04 13:12
page.s842.00 B08-01-04 22:34
<tools>0.00 B04-10-07 15:01
build.c8.12 kB02-09-04 13:12
...
Sponsored links

malloc.c (286.77 kB)

Need 1 point
Your Point(s)

Your Point isn't enough.

Get point immediately by PayPal

More(Debit card / Credit card / PayPal Credit / Online Banking)

Submit your source codes. Get more point

LOGIN

Don't have an account? Register now
Need any help?
Mail to: support@codeforge.com

切换到中文版?

CodeForge Chinese Version
CodeForge English Version

Where are you going?

^_^"Oops ...

Sorry!This guy is mysterious, its blog hasn't been opened, try another, please!
OK

Warm tip!

CodeForge to FavoriteFavorite by Ctrl+D