| malloc.ms (18568) | malloc.ms (18684) |
|---|---|
| 1.\" 2.\" ---------------------------------------------------------------------------- 3.\" "THE BEER-WARE LICENSE" (Revision 42): 4.\" <phk@login.dknet.dk> wrote this file. As long as you retain this notice you 5.\" can do whatever you want with this stuff. If we meet some day, and you think 6.\" this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp 7.\" ---------------------------------------------------------------------------- 8.\" | 1.\" 2.\" ---------------------------------------------------------------------------- 3.\" "THE BEER-WARE LICENSE" (Revision 42): 4.\" <phk@login.dknet.dk> wrote this file. As long as you retain this notice you 5.\" can do whatever you want with this stuff. If we meet some day, and you think 6.\" this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp 7.\" ---------------------------------------------------------------------------- 8.\" |
| 9.\" $Id: malloc.ms,v 1.1 1996/04/13 08:30:17 phk Exp $ | 9.\" $Id: malloc.ms,v 1.2 1996/09/29 18:36:13 phk Exp $ |
| 10.\" 11.ds RH Malloc and free 12.NH 13Malloc and free 14.PP 15The job of malloc(3) is to turn the rather simple 16brk(2) facility into a service programs can 17actually use without getting hurt. --- 27 unchanged lines hidden (view full) --- 45needed, read in the data and adjust the size of the chunk to match the 46size of the data read using realloc(3). 47.PP 48For reasons of efficiency, the original implementation of malloc(3) 49put the small structure used to contain the next and previous pointers 50plus the state of the chunk right before the chunk itself. 51.PP 52As a matter of fact, the canonical malloc(3) implementation can be | 10.\" 11.ds RH Malloc and free 12.NH 13Malloc and free 14.PP 15The job of malloc(3) is to turn the rather simple 16brk(2) facility into a service programs can 17actually use without getting hurt. --- 27 unchanged lines hidden (view full) --- 45needed, read in the data and adjust the size of the chunk to match the 46size of the data read using realloc(3). 47.PP 48For reasons of efficiency, the original implementation of malloc(3) 49put the small structure used to contain the next and previous pointers 50plus the state of the chunk right before the chunk itself. 51.PP 52As a matter of fact, the canonical malloc(3) implementation can be |
| 53studied in the ``Old testament'', chapter 8 verse 7 [Kernighan & Rich ie] | 53studied in the ``Old testament'', chapter 8 verse 7 [Kernighan & Ritchie] |
| 54.PP 55Various optimisations can be applied to the above basic algorithm: 56.IP 57If in freeing a chunk, we end up with the last chunk on the list being 58free, we can return that to the kernel by calling brk(2) with the first 59address of that chunk and then make the previous chunk the last on the 60chain by terminating its ``next'' pointer. 61.IP 62A best-fit algorithm can be used instead of first-fit at an expense 63of memory, because statistically fewer chances to brk(2) backwards will 64present themselves. 65.IP 66Splitting the list in two, once for used and one for free chunks to 67speed the searching. 68.IP 69Putting free chunks on one of several free-list depending on the size 70to speed allocation. 71.IP 72\&... | 54.PP 55Various optimisations can be applied to the above basic algorithm: 56.IP 57If in freeing a chunk, we end up with the last chunk on the list being 58free, we can return that to the kernel by calling brk(2) with the first 59address of that chunk and then make the previous chunk the last on the 60chain by terminating its ``next'' pointer. 61.IP 62A best-fit algorithm can be used instead of first-fit at an expense 63of memory, because statistically fewer chances to brk(2) backwards will 64present themselves. 65.IP 66Splitting the list in two, once for used and one for free chunks to 67speed the searching. 68.IP 69Putting free chunks on one of several free-list depending on the size 70to speed allocation. 71.IP 72\&... |