site_archiver@lists.apple.com Delivered-To: darwin-kernel@lists.apple.com But we give you so many other memory allocators to choose from (-: S+E -- Quinn "The Eskimo!" <http://www.apple.com/developer/> Apple Developer Technical Support * Networking, Communications, Hardware Mac OS X 10.4 +++++++++++++ MALLOC(<lvar> space, <type> cast, size_t size, int type, int flags) macro include: <sys/malloc.h> declared: xnu/bsd/sys/malloc.h implemented: xnu/bsd/sys/malloc.h zero size: non-NULL summary: just calls through to _MALLOC FREE(void *addr, int type) macro include: <sys/malloc.h> declared: xnu/bsd/sys/malloc.h implemented: xnu/bsd/sys/malloc.h NULL addr: NOP summary: just calls through to _FREE MALLOC_ZONE(<lvar> space, <type> cast, size_t size, int type, int flags) macro include: <sys/malloc.h> declared: xnu/bsd/sys/malloc.h implemented: xnu/bsd/sys/malloc.h zero size: non-NULL? summary: just calls through to _MALLOC_ZONE FREE_ZONE(void *addr, size_t size, int type) macro include: <sys/malloc.h> declared: xnu/bsd/sys/malloc.h implemented: xnu/bsd/sys/malloc.h NULL addr: NOP? summary: just calls through to _FREE_ZONE void * _MALLOC(size_t size, int type, int flags); function include: <sys/malloc.h> declared: xnu/bsd/sys/malloc.h implemented: xnu/bsd/kern/kern_malloc.c zero size: non-NULL summary: calls kalloc_noblock, if M_NOWAIT calls kalloc, otherwise keeps track of size, so that you don't have to provide it on _FREE void _FREE(void *addr, int type); function include: <sys/malloc.h> declared: xnu/bsd/sys/malloc.h implemented: xnu/bsd/kern/kern_malloc.c NULL addr: NOP summary: calls kfree uses header attached by _MALLOC to get size void * _MALLOC_ZONE(size_t size, int type, int flags); function include: <sys/malloc.h> declared: xnu/bsd/sys/malloc.h implemented: xnu/bsd/kern/kern_malloc.c zero size: non-NULL? summary: maintains zones for common BSD element types, eg M_MBUF kmzones array KMZ_CREATEZONE means create the zone for BSD KMZ_LOOKUPZONE means lookup Mach's zone of equivalent size calls zalloc_noblock, if element matches zone element size, and M_NOWAIT calls zalloc, if element matches zone element size, otherwise like _MALLOC, otherwise void _FREE_ZONE(void *elem, size_t size, int type) function include: <sys/malloc.h> declared: xnu/bsd/sys/malloc.h implemented: xnu/bsd/kern/kern_malloc.c NULL addr: NOP? summary: calls zfree, if size matches zone size calls kfree, otherwise * * * I/O Kit ======= void * IOMalloc(vm_size_t size); function include: <IOKit/IOLib.h> declared: xnu/iokit/IOKit/IOLib.h implemented: xnu/iokit/Kernel/IOLib.c zero size: non-NULL summary: calls kalloc void IOFree(void * address, vm_size_t size); function include: <IOKit/IOLib.h> declared: xnu/iokit/IOKit/IOLib.h implemented: xnu/iokit/Kernel/IOLib.c NULL addr: NOP summary: calls kfree void * IOMallocAligned(vm_size_t size, vm_size_t alignment); function include: <IOKit/IOLib.h> declared: xnu/iokit/IOKit/IOLib.h implemented: xnu/iokit/Kernel/IOLib.c zero size: NULL summary: kalloc, if size (plus tracking info) less than a page kernel_memory_allocate from kernel_map, otherwise void IOFreeAligned(void * address, vm_size_t size); function include: <IOKit/IOLib.h> declared: xnu/iokit/IOKit/IOLib.h implemented: xnu/iokit/Kernel/IOLib.c NULL addr: NOP summary: calls kfree, if size (plus tracking info) less than a page calls kmem_free, otherwise void IOFreeContiguous(void * address, vm_size_t size); function include: <IOKit/IOLib.h> declared: xnu/iokit/IOKit/IOLib.h implemented: xnu/iokit/Kernel/IOLib.c NULL addr: NOP summary: calls kfree, if size (plus tracking info) less than a page calls kmem_free, otherwise * * * libkern, OSMalloc ================= void * OSMalloc(uint32_t size, OSMallocTag tag); function include: <libkern/OSMalloc.h> declared: xnu/libkern/libkern/OSMalloc.h implemented: xnu/osfmk/kern/kalloc.c zero size: ??? (in the pageable case) summary: calls kmem_alloc_pageable, if tag is pageable and size a page or more calls kalloc, otherwise extern void * OSMalloc_nowait(uint32_t size, OSMallocTag tag); function include: <libkern/OSMalloc.h> declared: xnu/libkern/libkern/OSMalloc.h implemented: xnu/osfmk/kern/kalloc.c zero size: non-NULL summary: calls kalloc_noblock extern void * OSMalloc_noblock(uint32_t size, OSMallocTag tag); function include: <libkern/OSMalloc.h> declared: xnu/libkern/libkern/OSMalloc.h implemented: xnu/osfmk/kern/kalloc.c zero size: non-NULL summary: calls kalloc_noblock extern void OSFree(void * addr, uint32_t size, OSMallocTag tag); function include: <libkern/OSMalloc.h> declared: xnu/libkern/libkern/OSMalloc.h implemented: xnu/osfmk/kern/kalloc.c NULL addr: crash summary: calls kmem_free, if tag is pageable and size a page or more calls kfree, otherwise libkern, C++ ============ static void * OSObject::operator new(size_t size); function include: <libkern/c++/OSObject.h> declared: xnu/libkern/libkern/c++/OSObject.h implemented: xnu/libkern/c++/OSObject.cpp zero size: non-NULL summary: calls kalloc static void OSObject::operator delete(void *mem, size_t size); function include: <libkern/c++/OSObject.h> declared: xnu/libkern/libkern/c++/OSObject.h implemented: xnu/libkern/c++/OSObject.cpp NULL addr: crash? (protected by C++ runtime?) summary: calls kfree * * * Mach, kalloc ============ does all large allocations within kalloc_map, 16 MB submap of the kernel map void *kalloc(vm_size_t size); function include: n/a declared: xnu/osfmk/kern/kalloc.h implemented: xnu/osfmk/kern/kalloc.c zero size: non-NULL summary: calls kalloc_canblock with canblock set void *kalloc_noblock(vm_size_t size); function include: n/a declared: xnu/osfmk/kern/kalloc.h implemented: xnu/osfmk/kern/kalloc.c zero size: non-NULL summary: calls kalloc_canblock with canblock clear void *kalloc_canblock(vm_size_t size, boolean_t canblock); function include: n/a declared: none implemented: xnu/osfmk/kern/kalloc.c zero size: non-NULL summary: maintains zones of power of two sizes up to 8 KB k_zone array calls kmem_alloc in kalloc_map, if size large (kalloc_max_prerounded, 8 KB) calls zalloc_canblock(k_zone[zindex], ...), otherwise void *kget(vm_size_t size); function include: n/a declared: xnu/osfmk/kern/kalloc.h implemented: xnu/osfmk/kern/kalloc.c zero size: non-NULL summary: uses same same k_zone array as kalloc calls zget(k_zone[zindex]) void kfree(void *data, vm_size_t size); function include: n/a declared: xnu/osfmk/kern/kalloc.h implemented: xnu/osfmk/kern/kalloc.c NULL addr: crash summary: calls kmem_free to kalloc_map, if size large (kalloc_max_prerounded, 8 KB) calls zfree(k_zone[zindex], ...), otherwise * * * void * zalloc(zone_t zone); function include: n/a declared: xnu/osfmk/kern/zalloc.h implemented: xnu/osfmk/kern/zalloc.c zero size: n/a summary: calls zalloc_canblock with canblock set void * zalloc_noblock(zone_t zone); function include: n/a declared: xnu/osfmk/kern/zalloc.h implemented: xnu/osfmk/kern/zalloc.c zero size: n/a summary: calls zalloc_canblock with canblock clear void * zalloc_canblock(zone_t zone, boolean_t canblock); function include: n/a declared: xnu/osfmk/kern/zalloc.h implemented: xnu/osfmk/kern/zalloc.c zero size: n/a summary: tries to dequeue an element from the zone's free list kmem_alloc_wired(kernel_map, ...), zfill for initial space kernel_memory_allocate(zone_map, ...), expansion? void * zget(zone_t zone); function include: n/a declared: xnu/osfmk/kern/zalloc.h implemented: xnu/osfmk/kern/zalloc.c zero size: n/a summary: just gets a block from a zone's free list will never try to expand the zone void zfree(zone_t zone, void *elem); function include: n/a declared: xnu/osfmk/kern/zalloc.h implemented: xnu/osfmk/kern/zalloc.c NULL addr: crash summary: queues the element on the zone's free list kicks off the garbage collector if appropriate * * * Mach, kmem ========== kern_return_t kmem_alloc(vm_map_t map, vm_offset_t *addrp, vm_size_t size); function include: n/a declared: xnu/osfmk/vm/vm_kern.h implemented: xnu/osfmk/vm/vm_kern.c zero size: error summary: calls kernel_memory_allocate(map, addrp, size, 0, 0) void kmem_free( vm_map_t map, vm_offset_t addr, vm_size_t size) function include: n/a declared: xnu/osfmk/vm/vm_kern.h implemented: xnu/osfmk/vm/vm_kern.c NULL addr: not sure, but it looks like a really bad idea summary: vm_map_remove _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-kernel mailing list (Darwin-kernel@lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-kernel/site_archiver%40lists.a... At 20:06 -0800 30/1/06, Herbert wrote: P.S. Bad Apple, for moving kmem_alloc to a private place, and removing it's symbol!!! I've did a bunch of research into kernel memory allocation over the last couple of years. I took copious notes, which I haven't had time to productise yet. I've pasted my notes into the end of this email. I hope folks find them useful. btw I highly recommend using Graphviz to render the diagram. The resulting graph really illuminates the kernel memory allocation Big Picture (tm). Layering ======== If you paste the following into a Graphviz <http://www.pixelglow.com/graphviz/> document, you'll get a nice graph of the dependencies between each layer. ------------------------------------------------------------------------ digraph "Kernel Memory Allocators" { label = "Kernel Memory Allocators"; labelloc = t; labeljust = c; fontsize = 24; ranksep = 2; // BSD subgraph cluster0 { label = "BSD\n<sys/malloc.h>\nKPI"; fontsize = 14; style = bold; MALLOC; _MALLOC; MALLOC_ZONE; _MALLOC_ZONE; } MALLOC -> _MALLOC; _MALLOC -> kalloc; _MALLOC -> kalloc_noblock [label="M_NOWAIT",fontsize=8]; MALLOC_ZONE -> _MALLOC_ZONE; _MALLOC_ZONE -> zalloc_noblock [label="M_NOWAIT and\nzone size match",fontsize=8]; _MALLOC_ZONE -> zalloc [label="zone size match",fontsize=8]; _MALLOC_ZONE -> kalloc; _MALLOC_ZONE -> kalloc_noblock [label="M_NOWAIT",fontsize=8]; // I/O Kit subgraph cluster1 { label = "I/O Kit\n<IOKit/IOLib.h>\nKPI"; fontsize = 14; style = bold; IOMalloc; IOMallocAligned; IOMallocContiguous; } IOMalloc -> kalloc; IOMallocAligned -> kalloc [label="less than\npage size",fontsize=8]; IOMallocAligned -> kernel_memory_allocate [label="greater than\npage size",fontsize=8]; IOMallocContiguous -> kalloc [label="less than\npage size",fontsize=8]; IOMallocContiguous -> kernel_memory_allocate [label="exactly\npage size",fontsize=8]; IOMallocContiguous -> kmem_alloc_contig [label="greater than\npage size",fontsize=8]; // libkern subgraph cluster2 { label = "libkern\n<libkern/OSMalloc.h>\nKPI"; fontsize = 14; style = bold; OSMalloc; OSMalloc_nowait; OSMalloc_noblock; "OSObject::operator new"; } OSMalloc -> kalloc; OSMalloc -> kmem_alloc_pageable [label="greater than page size\nand OSMT_PAGEABLE",fontsize=8]; OSMalloc_nowait -> kalloc_noblock; OSMalloc_noblock -> kalloc_noblock; "OSObject::operator new" -> kalloc; // Mach, kalloc subgraph cluster4 { label = "Mach, kalloc"; fontsize = 14; kalloc; kalloc_canblock; kalloc_noblock; } kalloc -> kalloc_canblock; kalloc_noblock -> kalloc_canblock; kalloc_canblock -> zalloc_canblock [label="fits in zone;\nthat is, less than 8 KB",fontsize=8]; kalloc_canblock -> kmem_alloc [label="bigger than largest zone;\nin kalloc_map submap (16 MB)",fontsize=8]; // Mach, Zone subgraph cluster5 { label = "Mach, zalloc"; fontsize = 14; zalloc; zalloc_canblock; zalloc_noblock; } zalloc -> zalloc_canblock; zalloc_noblock -> zalloc_canblock; zalloc_canblock -> kmem_alloc_wired; zalloc_canblock -> kernel_memory_allocate; // Mach, kmem subgraph cluster6 { label = "Mach, kmem"; fontsize = 14; kmem_alloc; kmem_alloc_aligned; kmem_alloc_wired; kmem_alloc_contig; kmem_alloc_pageable; kernel_memory_allocate; } kmem_alloc -> kernel_memory_allocate; kmem_alloc_aligned -> kernel_memory_allocate; kmem_alloc_wired -> kernel_memory_allocate; } ------------------------------------------------------------------------ BSD === in the BSD allocators, type is one of the M_XXX constants from <sys/malloc.h> (use M_TEMP for miscellaneous allocations) and flags is a bit field made up of bits M_NOWAIT and M_ZERO (only supported by [_]MALLOC; not supported by [_]MALLOC_ZONE) void * IOMallocContiguous(vm_size_t size, vm_size_t alignment, IOPhysicalAddress * physicalAddress); function include: <IOKit/IOLib.h> declared: xnu/iokit/IOKit/IOLib.h implemented: xnu/iokit/Kernel/IOLib.c zero size: NULL summary: calls kalloc, if size (plus tracking info) less than a page calls kernel_memory_allocate from kernel_map, if size exactly a page calls kmem_alloc_contig from kernel_map, otherwise Mach, zalloc ============ uses kmem_suballoc to create a contiguous area (zone_map) in kernel_map for all zone use; set set by zsize boot arg (in MB), otherwise 1/4 of physical memory lots of complex stuff (garbage collect, pageable zones, etc) that I didn't investigate kern_return_t kmem_alloc_aligned(vm_map_t map, vm_offset_t *addrp, vm_size_t size); function include: n/a declared: xnu/osfmk/vm/vm_kern.h implemented: xnu/osfmk/vm/vm_kern.c zero size: error summary: calls kernel_memory_allocate(map, addrp, size, size - 1, KMA_KOBJECT) kern_return_t kmem_alloc_wired(vm_map_t map, vm_offset_t *addrp, vm_size_t size); function include: n/a declared: xnu/osfmk/vm/vm_kern.h implemented: xnu/osfmk/vm/vm_kern.c zero size: error summary: calls kernel_memory_allocate(map, addrp, size, 0, KMA_KOBJECT) kern_return_t kmem_alloc_contig(vm_map_t map, vm_offset_t *addrp, vm_size_t size, vm_offset_t mask, int flags); function include: n/a declared: xnu/osfmk/vm/vm_kern.h implemented: xnu/osfmk/vm/vm_kern.c zero size: error summary: if KMA_KOBJECT use kernel_object backing object else use new backing object vm_map_find_space to find space in map cpm_allocate to allocate pages vm_page_insert to insert pages into object vm_map_wire release reference to backing object kern_return_t kernel_memory_allocate(vm_map_t map, vm_offset_t *addrp, vm_size_t size, vm_offset_t mask, int flags); function include: n/a declared: xnu/osfmk/vm/vm_kern.h implemented: xnu/osfmk/vm/vm_kern.c zero size: error summary: if KMA_KOBJECT use kernel_object backing object else use new backing object vm_map_find_space to find space in map vm_page_alloc to populate pages vm_map_wire release reference to backing object (sneaky) kern_return_t kmem_kmem_alloc_pageable(vm_map_t map, vm_offset_t *addrp, vm_size_t size); function include: n/a declared: xnu/osfmk/vm/vm_kern.h implemented: xnu/osfmk/vm/vm_kern.c zero size: ??? summary: vm_map_enter This email sent to site_archiver@lists.apple.com