Re: kmem_alloc replacement in Tiger
Re: kmem_alloc replacement in Tiger
- Subject: Re: kmem_alloc replacement in Tiger
- From: Quinn <email@hidden>
- Date: Wed, 1 Feb 2006 14:29:04 +0000
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!!!
But we give you so many other memory allocators to choose from (-:
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).
S+E
--
Quinn "The Eskimo!" <http://www.apple.com/developer/>
Apple Developer Technical Support * Networking, Communications, Hardware
Mac OS X 10.4
+++++++++++++
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)
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 * 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
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
* * *
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
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)
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
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 (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden