Date: Wed, 20 Aug 2008 08:24:49 GMT From: John Birrell <jb@FreeBSD.org> To: Perforce Change Reviews <perforce@freebsd.org> Subject: PERFORCE change 147894 for review Message-ID: <200808200824.m7K8OnfI021838@repoman.freebsd.org>
next in thread | raw e-mail | index | archive | help
http://perforce.freebsd.org/chv.cgi?CH=147894 Change 147894 by jb@freebsd3 on 2008/08/20 08:23:55 IF7 Affected files ... .. //depot/projects/dtrace7/src/lib/libc/stdlib/malloc.c#4 integrate .. //depot/projects/dtrace7/src/release/doc/en_US.ISO8859-1/errata/article.sgml#4 integrate .. //depot/projects/dtrace7/src/sbin/ifconfig/ifconfig.8#4 integrate .. //depot/projects/dtrace7/src/sbin/ifconfig/ifieee80211.c#3 integrate .. //depot/projects/dtrace7/src/sbin/ipfw/ipfw.8#8 integrate .. //depot/projects/dtrace7/src/share/man/man4/bpf.4#2 integrate .. //depot/projects/dtrace7/src/share/man/man9/locking.9#2 integrate .. //depot/projects/dtrace7/src/share/zoneinfo/Theory#2 delete .. //depot/projects/dtrace7/src/share/zoneinfo/africa#2 integrate .. //depot/projects/dtrace7/src/share/zoneinfo/asia#4 integrate .. //depot/projects/dtrace7/src/share/zoneinfo/australasia#2 integrate .. //depot/projects/dtrace7/src/share/zoneinfo/europe#3 integrate .. //depot/projects/dtrace7/src/share/zoneinfo/leapseconds#3 integrate .. //depot/projects/dtrace7/src/share/zoneinfo/northamerica#4 integrate .. //depot/projects/dtrace7/src/share/zoneinfo/southamerica#4 integrate .. //depot/projects/dtrace7/src/share/zoneinfo/zone.tab#4 integrate .. //depot/projects/dtrace7/src/sys/amd64/amd64/cpu_switch.S#2 integrate .. //depot/projects/dtrace7/src/sys/amd64/amd64/genassym.c#2 integrate .. //depot/projects/dtrace7/src/sys/amd64/ia32/ia32_signal.c#3 integrate .. //depot/projects/dtrace7/src/sys/amd64/include/pcb.h#2 integrate .. //depot/projects/dtrace7/src/sys/amd64/linux32/linux32_machdep.c#3 integrate .. //depot/projects/dtrace7/src/sys/boot/i386/boot2/boot2.c#4 integrate .. //depot/projects/dtrace7/src/sys/boot/i386/btx/btx/btx.S#3 integrate .. //depot/projects/dtrace7/src/sys/boot/i386/gptboot/gptboot.c#3 integrate .. //depot/projects/dtrace7/src/sys/boot/i386/loader/main.c#2 integrate .. //depot/projects/dtrace7/src/sys/boot/pc98/loader/main.c#2 integrate .. //depot/projects/dtrace7/src/sys/contrib/pf/net/pf.c#4 integrate .. //depot/projects/dtrace7/src/sys/dev/ath/ah_osdep.h#2 integrate .. //depot/projects/dtrace7/src/sys/dev/cxgb/ulp/tom/cxgb_cpl_socket.c#2 integrate .. //depot/projects/dtrace7/src/sys/dev/iwi/if_iwi.c#3 integrate .. //depot/projects/dtrace7/src/sys/dev/mii/brgphy.c#4 integrate .. //depot/projects/dtrace7/src/sys/dev/nfe/if_nfe.c#6 integrate .. //depot/projects/dtrace7/src/sys/dev/nfe/if_nfereg.h#3 integrate .. //depot/projects/dtrace7/src/sys/dev/nfe/if_nfevar.h#2 integrate .. //depot/projects/dtrace7/src/sys/dev/nvram/nvram.c#2 integrate .. //depot/projects/dtrace7/src/sys/dev/pci/pci.c#4 integrate .. //depot/projects/dtrace7/src/sys/dev/re/if_re.c#9 integrate .. //depot/projects/dtrace7/src/sys/dev/sk/if_sk.c#3 integrate .. //depot/projects/dtrace7/src/sys/dev/sk/if_skreg.h#2 integrate .. //depot/projects/dtrace7/src/sys/dev/usb/if_rum.c#3 integrate .. //depot/projects/dtrace7/src/sys/dev/usb/usbdevs#11 integrate .. //depot/projects/dtrace7/src/sys/fs/devfs/devfs_int.h#2 integrate .. //depot/projects/dtrace7/src/sys/fs/devfs/devfs_vnops.c#4 integrate .. //depot/projects/dtrace7/src/sys/i386/i386/pmap.c#6 integrate .. //depot/projects/dtrace7/src/sys/kern/kern_conf.c#8 integrate .. //depot/projects/dtrace7/src/sys/kern/kern_descrip.c#7 integrate .. //depot/projects/dtrace7/src/sys/kern/kern_mbuf.c#4 integrate .. //depot/projects/dtrace7/src/sys/kern/kern_thread.c#8 integrate .. //depot/projects/dtrace7/src/sys/kern/sched_4bsd.c#6 integrate .. //depot/projects/dtrace7/src/sys/kern/subr_stack.c#3 integrate .. //depot/projects/dtrace7/src/sys/kern/subr_witness.c#5 integrate .. //depot/projects/dtrace7/src/sys/kern/tty_pts.c#4 integrate .. //depot/projects/dtrace7/src/sys/kern/tty_pty.c#6 integrate .. //depot/projects/dtrace7/src/sys/net/bpf.c#6 integrate .. //depot/projects/dtrace7/src/sys/net/bpf.h#2 integrate .. //depot/projects/dtrace7/src/sys/net80211/ieee80211.h#4 integrate .. //depot/projects/dtrace7/src/sys/net80211/ieee80211_input.c#3 integrate .. //depot/projects/dtrace7/src/sys/net80211/ieee80211_input.h#1 branch .. //depot/projects/dtrace7/src/sys/net80211/ieee80211_ioctl.c#2 integrate .. //depot/projects/dtrace7/src/sys/net80211/ieee80211_node.c#3 integrate .. //depot/projects/dtrace7/src/sys/net80211/ieee80211_node.h#2 integrate .. //depot/projects/dtrace7/src/sys/net80211/ieee80211_output.c#4 integrate .. //depot/projects/dtrace7/src/sys/net80211/ieee80211_proto.h#2 integrate .. //depot/projects/dtrace7/src/sys/net80211/ieee80211_scan.h#2 integrate .. //depot/projects/dtrace7/src/sys/net80211/ieee80211_scan_sta.c#4 integrate .. //depot/projects/dtrace7/src/sys/netinet/if_ether.c#3 integrate .. //depot/projects/dtrace7/src/sys/netinet/in_mcast.c#4 integrate .. //depot/projects/dtrace7/src/sys/netinet/in_pcb.c#6 integrate .. //depot/projects/dtrace7/src/sys/netinet/in_pcb.h#4 integrate .. //depot/projects/dtrace7/src/sys/netinet/ip_divert.c#2 integrate .. //depot/projects/dtrace7/src/sys/netinet/ip_fw2.c#6 integrate .. //depot/projects/dtrace7/src/sys/netinet/ip_options.c#4 integrate .. //depot/projects/dtrace7/src/sys/netinet/ip_output.c#4 integrate .. //depot/projects/dtrace7/src/sys/netinet/raw_ip.c#4 integrate .. //depot/projects/dtrace7/src/sys/netinet/tcp_input.c#5 integrate .. //depot/projects/dtrace7/src/sys/netinet/tcp_output.c#6 integrate .. //depot/projects/dtrace7/src/sys/netinet/tcp_reass.c#2 integrate .. //depot/projects/dtrace7/src/sys/netinet/tcp_sack.c#2 integrate .. //depot/projects/dtrace7/src/sys/netinet/tcp_subr.c#4 integrate .. //depot/projects/dtrace7/src/sys/netinet/tcp_syncache.c#8 integrate .. //depot/projects/dtrace7/src/sys/netinet/tcp_timer.c#3 integrate .. //depot/projects/dtrace7/src/sys/netinet/tcp_timewait.c#2 integrate .. //depot/projects/dtrace7/src/sys/netinet/tcp_usrreq.c#5 integrate .. //depot/projects/dtrace7/src/sys/netinet/udp_usrreq.c#3 integrate .. //depot/projects/dtrace7/src/sys/netinet6/icmp6.c#2 integrate .. //depot/projects/dtrace7/src/sys/netinet6/in6_pcb.c#5 integrate .. //depot/projects/dtrace7/src/sys/netinet6/in6_src.c#4 integrate .. //depot/projects/dtrace7/src/sys/netinet6/ip6_input.c#3 integrate .. //depot/projects/dtrace7/src/sys/netinet6/ip6_var.h#4 integrate .. //depot/projects/dtrace7/src/sys/netinet6/raw_ip6.c#4 integrate .. //depot/projects/dtrace7/src/sys/netinet6/udp6_usrreq.c#4 integrate .. //depot/projects/dtrace7/src/sys/security/audit/audit_arg.c#4 integrate .. //depot/projects/dtrace7/src/sys/security/mac/mac_inet.c#4 integrate .. //depot/projects/dtrace7/src/sys/sparc64/include/atomic.h#3 integrate .. //depot/projects/dtrace7/src/sys/sun4v/include/atomic.h#3 integrate .. //depot/projects/dtrace7/src/sys/sys/conf.h#4 integrate .. //depot/projects/dtrace7/src/sys/sys/file.h#2 integrate .. //depot/projects/dtrace7/src/sys/sys/proc.h#9 integrate .. //depot/projects/dtrace7/src/sys/vm/uma.h#2 integrate .. //depot/projects/dtrace7/src/sys/vm/uma_core.c#2 integrate .. //depot/projects/dtrace7/src/tools/tools/nanobsd/nanobsd.sh#2 integrate .. //depot/projects/dtrace7/src/usr.bin/make/main.c#4 integrate .. //depot/projects/dtrace7/src/usr.bin/make/make.1#3 integrate .. //depot/projects/dtrace7/src/usr.sbin/adduser/rmuser.sh#2 integrate .. //depot/projects/dtrace7/src/usr.sbin/newsyslog/newsyslog.conf.5#3 integrate .. //depot/projects/dtrace7/src/usr.sbin/sysinstall/dist.c#4 integrate .. //depot/projects/dtrace7/src/usr.sbin/sysinstall/dist.h#4 integrate .. //depot/projects/dtrace7/src/usr.sbin/sysinstall/menus.c#5 integrate .. //depot/projects/dtrace7/src/usr.sbin/syslogd/syslog.conf.5#2 integrate .. //depot/projects/dtrace7/src/usr.sbin/syslogd/syslogd.c#3 integrate Differences ... ==== //depot/projects/dtrace7/src/lib/libc/stdlib/malloc.c#4 (text+ko) ==== @@ -70,9 +70,9 @@ * | | 8 kB | * | | 12 kB | * | | ... | - * | | 1008 kB | * | | 1012 kB | * | | 1016 kB | + * | | 1020 kB | * |=====================================| * | Huge | 1 MB | * | | 2 MB | @@ -128,7 +128,7 @@ #define MALLOC_DSS #include <sys/cdefs.h> -__FBSDID("$FreeBSD: src/lib/libc/stdlib/malloc.c,v 1.147.2.3 2008/06/16 23:42:05 jasone Exp $"); +__FBSDID("$FreeBSD: src/lib/libc/stdlib/malloc.c,v 1.147.2.4 2008/08/16 20:14:21 jasone Exp $"); #include "libc_private.h" #ifdef MALLOC_DEBUG @@ -292,11 +292,7 @@ #define RUN_MAX_OVRHD 0x0000003dU #define RUN_MAX_OVRHD_RELAX 0x00001800U -/* - * Put a cap on small object run size. This overrides RUN_MAX_OVRHD. Note - * that small runs must be small enough that page offsets can fit within the - * CHUNK_MAP_POS_MASK bits. - */ +/* Put a cap on small object run size. This overrides RUN_MAX_OVRHD. */ #define RUN_MAX_SMALL_2POW 15 #define RUN_MAX_SMALL (1U << RUN_MAX_SMALL_2POW) @@ -444,8 +440,10 @@ /* Tree of extents. */ typedef struct extent_node_s extent_node_t; struct extent_node_s { +#ifdef MALLOC_DSS /* Linkage for the size/address-ordered tree. */ rb_node(extent_node_t) link_szad; +#endif /* Linkage for the address-ordered tree. */ rb_node(extent_node_t) link_ad; @@ -466,15 +464,67 @@ typedef struct arena_s arena_t; typedef struct arena_bin_s arena_bin_t; -/* - * Each map element contains several flags, plus page position for runs that - * service small allocations. - */ -typedef uint8_t arena_chunk_map_t; -#define CHUNK_MAP_UNTOUCHED 0x80U -#define CHUNK_MAP_DIRTY 0x40U -#define CHUNK_MAP_LARGE 0x20U -#define CHUNK_MAP_POS_MASK 0x1fU +/* Each element of the chunk map corresponds to one page within the chunk. */ +typedef struct arena_chunk_map_s arena_chunk_map_t; +struct arena_chunk_map_s { + /* + * Linkage for run trees. There are two disjoint uses: + * + * 1) arena_t's runs_avail tree. + * 2) arena_run_t conceptually uses this linkage for in-use non-full + * runs, rather than directly embedding linkage. + */ + rb_node(arena_chunk_map_t) link; + + /* + * Run address (or size) and various flags are stored together. The bit + * layout looks like (assuming 32-bit system): + * + * ???????? ???????? ????---- ---kdzla + * + * ? : Unallocated: Run address for first/last pages, unset for internal + * pages. + * Small: Run address. + * Large: Run size for first page, unset for trailing pages. + * - : Unused. + * k : key? + * d : dirty? + * z : zeroed? + * l : large? + * a : allocated? + * + * Following are example bit patterns for the three types of runs. + * + * r : run address + * s : run size + * x : don't care + * - : 0 + * [dzla] : bit set + * + * Unallocated: + * ssssssss ssssssss ssss---- -------- + * xxxxxxxx xxxxxxxx xxxx---- ----d--- + * ssssssss ssssssss ssss---- -----z-- + * + * Small: + * rrrrrrrr rrrrrrrr rrrr---- -------a + * rrrrrrrr rrrrrrrr rrrr---- -------a + * rrrrrrrr rrrrrrrr rrrr---- -------a + * + * Large: + * ssssssss ssssssss ssss---- ------la + * -------- -------- -------- ------la + * -------- -------- -------- ------la + */ + size_t bits; +#define CHUNK_MAP_KEY ((size_t)0x10U) +#define CHUNK_MAP_DIRTY ((size_t)0x08U) +#define CHUNK_MAP_ZEROED ((size_t)0x04U) +#define CHUNK_MAP_LARGE ((size_t)0x02U) +#define CHUNK_MAP_ALLOCATED ((size_t)0x01U) +}; +typedef rb_tree(arena_chunk_map_t) arena_avail_tree_t; +typedef rb_tree(arena_chunk_map_t) arena_run_tree_t; /* Arena chunk header. */ typedef struct arena_chunk_s arena_chunk_t; @@ -482,42 +532,19 @@ /* Arena that owns the chunk. */ arena_t *arena; - /* Linkage for the arena's chunks_all tree. */ - rb_node(arena_chunk_t) link_all; - /* Linkage for the arena's chunks_dirty tree. */ rb_node(arena_chunk_t) link_dirty; - /* - * Number of pages in use. This is maintained in order to make - * detection of empty chunks fast. - */ - size_t pages_used; - /* Number of dirty pages. */ size_t ndirty; - /* - * Tree of extent nodes that are embedded in the arena chunk header - * page(s). These nodes are used by arena_chunk_node_alloc(). - */ - extent_tree_t nodes; - extent_node_t *nodes_past; - - /* - * Map of pages within chunk that keeps track of free/large/small. For - * free runs, only the map entries for the first and last pages are - * kept up to date, so that free runs can be quickly coalesced. - */ + /* Map of pages within chunk that keeps track of free/large/small. */ arena_chunk_map_t map[1]; /* Dynamically sized. */ }; typedef rb_tree(arena_chunk_t) arena_chunk_tree_t; typedef struct arena_run_s arena_run_t; struct arena_run_s { - /* Linkage for run trees. */ - rb_node(arena_run_t) link; - #ifdef MALLOC_DEBUG uint32_t magic; # define ARENA_RUN_MAGIC 0x384adf93 @@ -535,7 +562,6 @@ /* Bitmask of in-use regions (0: in use, 1: free). */ unsigned regs_mask[1]; /* Dynamically sized. */ }; -typedef rb_tree(arena_run_t) arena_run_tree_t; struct arena_bin_s { /* @@ -587,19 +613,7 @@ arena_stats_t stats; #endif - /* Tree of all chunks this arena manages. */ - arena_chunk_tree_t chunks_all; - - /* - * Tree of dirty-page-containing chunks this arena manages. This tree - * is maintained in addition to chunks_all in order to make - * deallocation O(lg d), where 'd' is the size of chunks_dirty. - * - * Without this tree, deallocation would be O(a), where 'a' is the size - * of chunks_all. Since dirty pages are purged in descending memory - * order, it would not be difficult to trigger something approaching - * worst case behavior with a series of large deallocations. - */ + /* Tree of dirty-page-containing chunks this arena manages. */ arena_chunk_tree_t chunks_dirty; /* @@ -623,15 +637,10 @@ size_t ndirty; /* - * Trees of this arena's available runs. Two trees are maintained - * using one set of nodes, since one is needed for first-best-fit run - * allocation, and the other is needed for coalescing. + * Size/address-ordered tree of this arena's available runs. This tree + * is used for first-best-fit run allocation. */ - extent_tree_t runs_avail_szad; - extent_tree_t runs_avail_ad; - - /* Tree of this arena's allocated (in-use) runs. */ - extent_tree_t runs_alloced_ad; + arena_avail_tree_t runs_avail; #ifdef MALLOC_BALANCE /* @@ -880,22 +889,18 @@ #ifndef NO_TLS static arena_t *choose_arena_hard(void); #endif -static extent_node_t *arena_chunk_node_alloc(arena_chunk_t *chunk); -static void arena_chunk_node_dealloc(arena_chunk_t *chunk, - extent_node_t *node); static void arena_run_split(arena_t *arena, arena_run_t *run, size_t size, - bool small, bool zero); + bool large, bool zero); static arena_chunk_t *arena_chunk_alloc(arena_t *arena); static void arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk); -static arena_run_t *arena_run_alloc(arena_t *arena, size_t size, bool small, +static arena_run_t *arena_run_alloc(arena_t *arena, size_t size, bool large, bool zero); static void arena_purge(arena_t *arena); static void arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty); static void arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk, - extent_node_t *nodeB, arena_run_t *run, size_t oldsize, size_t newsize); + arena_run_t *run, size_t oldsize, size_t newsize); static void arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk, - extent_node_t *nodeA, arena_run_t *run, size_t oldsize, size_t newsize, - bool dirty); + arena_run_t *run, size_t oldsize, size_t newsize, bool dirty); static arena_run_t *arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin); static void *arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin); static size_t arena_bin_run_size_calc(arena_bin_t *bin, size_t min_run_size); @@ -1007,10 +1012,11 @@ /* Exponentially back off. */ for (i = 1; i <= SPIN_LIMIT_2POW; i++) { - for (j = 0; j < (1U << i); j++) + for (j = 0; j < (1U << i); j++) { ret++; + CPU_SPINWAIT; + } - CPU_SPINWAIT; if (_pthread_mutex_trylock(lock) == 0) return (ret); } @@ -1429,6 +1435,7 @@ * Begin extent tree code. */ +#ifdef MALLOC_DSS static inline int extent_szad_comp(extent_node_t *a, extent_node_t *b) { @@ -1450,6 +1457,7 @@ /* Wrap red-black tree macros in functions. */ rb_wrap(__unused static, extent_tree_szad_, extent_tree_t, extent_node_t, link_szad, extent_szad_comp) +#endif static inline int extent_ad_comp(extent_node_t *a, extent_node_t *b) @@ -2014,55 +2022,57 @@ } /* Wrap red-black tree macros in functions. */ -rb_wrap(__unused static, arena_chunk_tree_all_, arena_chunk_tree_t, - arena_chunk_t, link_all, arena_chunk_comp) rb_wrap(__unused static, arena_chunk_tree_dirty_, arena_chunk_tree_t, arena_chunk_t, link_dirty, arena_chunk_comp) static inline int -arena_run_comp(arena_run_t *a, arena_run_t *b) +arena_run_comp(arena_chunk_map_t *a, arena_chunk_map_t *b) { - uintptr_t a_run = (uintptr_t)a; - uintptr_t b_run = (uintptr_t)b; + uintptr_t a_mapelm = (uintptr_t)a; + uintptr_t b_mapelm = (uintptr_t)b; assert(a != NULL); assert(b != NULL); - return ((a_run > b_run) - (a_run < b_run)); + return ((a_mapelm > b_mapelm) - (a_mapelm < b_mapelm)); } /* Wrap red-black tree macros in functions. */ -rb_wrap(__unused static, arena_run_tree_, arena_run_tree_t, arena_run_t, link, - arena_run_comp) +rb_wrap(__unused static, arena_run_tree_, arena_run_tree_t, arena_chunk_map_t, + link, arena_run_comp) -static extent_node_t * -arena_chunk_node_alloc(arena_chunk_t *chunk) +static inline int +arena_avail_comp(arena_chunk_map_t *a, arena_chunk_map_t *b) { - extent_node_t *ret; + int ret; + size_t a_size = a->bits & ~pagesize_mask; + size_t b_size = b->bits & ~pagesize_mask; + + ret = (a_size > b_size) - (a_size < b_size); + if (ret == 0) { + uintptr_t a_mapelm, b_mapelm; + + if ((a->bits & CHUNK_MAP_KEY) == 0) + a_mapelm = (uintptr_t)a; + else { + /* + * Treat keys as though they are lower than anything + * else. + */ + a_mapelm = 0; + } + b_mapelm = (uintptr_t)b; - ret = extent_tree_ad_first(&chunk->nodes); - if (ret != NULL) - extent_tree_ad_remove(&chunk->nodes, ret); - else { - ret = chunk->nodes_past; - chunk->nodes_past = (extent_node_t *) - ((uintptr_t)chunk->nodes_past + sizeof(extent_node_t)); - assert((uintptr_t)ret + sizeof(extent_node_t) <= - (uintptr_t)chunk + (arena_chunk_header_npages << - pagesize_2pow)); + ret = (a_mapelm > b_mapelm) - (a_mapelm < b_mapelm); } return (ret); } -static void -arena_chunk_node_dealloc(arena_chunk_t *chunk, extent_node_t *node) -{ +/* Wrap red-black tree macros in functions. */ +rb_wrap(__unused static, arena_avail_tree_, arena_avail_tree_t, + arena_chunk_map_t, link, arena_avail_comp) - node->addr = (void *)node; - extent_tree_ad_insert(&chunk->nodes, node); -} - static inline void * arena_run_reg_alloc(arena_run_t *run, arena_bin_t *bin) { @@ -2200,8 +2210,8 @@ */ regind = diff / size; } - } else if (size <= ((sizeof(size_invs) / sizeof(unsigned)) - << QUANTUM_2POW_MIN) + 2) { + } else if (size <= (((sizeof(size_invs) / sizeof(unsigned)) + 2) + << QUANTUM_2POW_MIN)) { regind = size_invs[(size >> QUANTUM_2POW_MIN) - 3] * diff; regind >>= SIZE_INV_SHIFT; } else { @@ -2227,75 +2237,74 @@ } static void -arena_run_split(arena_t *arena, arena_run_t *run, size_t size, bool small, +arena_run_split(arena_t *arena, arena_run_t *run, size_t size, bool large, bool zero) { arena_chunk_t *chunk; size_t old_ndirty, run_ind, total_pages, need_pages, rem_pages, i; - extent_node_t *nodeA, *nodeB, key; - /* Insert a node into runs_alloced_ad for the first part of the run. */ chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); old_ndirty = chunk->ndirty; - nodeA = arena_chunk_node_alloc(chunk); - nodeA->addr = run; - nodeA->size = size; - extent_tree_ad_insert(&arena->runs_alloced_ad, nodeA); - - key.addr = run; - nodeB = extent_tree_ad_search(&arena->runs_avail_ad, &key); - assert(nodeB != NULL); - run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk) >> pagesize_2pow); - total_pages = nodeB->size >> pagesize_2pow; + total_pages = (chunk->map[run_ind].bits & ~pagesize_mask) >> + pagesize_2pow; need_pages = (size >> pagesize_2pow); assert(need_pages > 0); assert(need_pages <= total_pages); - assert(need_pages <= CHUNK_MAP_POS_MASK || small == false); rem_pages = total_pages - need_pages; + arena_avail_tree_remove(&arena->runs_avail, &chunk->map[run_ind]); + + /* Keep track of trailing unused pages for later use. */ + if (rem_pages > 0) { + chunk->map[run_ind+need_pages].bits = (rem_pages << + pagesize_2pow) | (chunk->map[run_ind+need_pages].bits & + pagesize_mask); + chunk->map[run_ind+total_pages-1].bits = (rem_pages << + pagesize_2pow) | (chunk->map[run_ind+total_pages-1].bits & + pagesize_mask); + arena_avail_tree_insert(&arena->runs_avail, + &chunk->map[run_ind+need_pages]); + } + for (i = 0; i < need_pages; i++) { /* Zero if necessary. */ if (zero) { - if ((chunk->map[run_ind + i] & CHUNK_MAP_UNTOUCHED) + if ((chunk->map[run_ind + i].bits & CHUNK_MAP_ZEROED) == 0) { memset((void *)((uintptr_t)chunk + ((run_ind + i) << pagesize_2pow)), 0, pagesize); - /* CHUNK_MAP_UNTOUCHED is cleared below. */ + /* CHUNK_MAP_ZEROED is cleared below. */ } } /* Update dirty page accounting. */ - if (chunk->map[run_ind + i] & CHUNK_MAP_DIRTY) { + if (chunk->map[run_ind + i].bits & CHUNK_MAP_DIRTY) { chunk->ndirty--; arena->ndirty--; + /* CHUNK_MAP_DIRTY is cleared below. */ } /* Initialize the chunk map. */ - if (small) - chunk->map[run_ind + i] = (uint8_t)i; - else - chunk->map[run_ind + i] = CHUNK_MAP_LARGE; + if (large) { + chunk->map[run_ind + i].bits = CHUNK_MAP_LARGE + | CHUNK_MAP_ALLOCATED; + } else { + chunk->map[run_ind + i].bits = (size_t)run + | CHUNK_MAP_ALLOCATED; + } } - /* Keep track of trailing unused pages for later use. */ - extent_tree_szad_remove(&arena->runs_avail_szad, nodeB); - if (rem_pages > 0) { - /* - * Update nodeB in runs_avail_*. Its position within - * runs_avail_ad does not change. - */ - nodeB->addr = (void *)((uintptr_t)nodeB->addr + size); - nodeB->size -= size; - extent_tree_szad_insert(&arena->runs_avail_szad, nodeB); - } else { - /* Remove nodeB from runs_avail_*. */ - extent_tree_ad_remove(&arena->runs_avail_ad, nodeB); - arena_chunk_node_dealloc(chunk, nodeB); - } + /* + * Set the run size only in the first element for large runs. This is + * primarily a debugging aid, since the lack of size info for trailing + * pages only matters if the application tries to operate on an + * interior pointer. + */ + if (large) + chunk->map[run_ind].bits |= size; - chunk->pages_used += need_pages; if (chunk->ndirty == 0 && old_ndirty > 0) arena_chunk_tree_dirty_remove(&arena->chunks_dirty, chunk); } @@ -2304,7 +2313,7 @@ arena_chunk_alloc(arena_t *arena) { arena_chunk_t *chunk; - extent_node_t *node; + size_t i; if (arena->spare != NULL) { chunk = arena->spare; @@ -2319,38 +2328,28 @@ chunk->arena = arena; - arena_chunk_tree_all_insert(&arena->chunks_all, chunk); - /* * Claim that no pages are in use, since the header is merely * overhead. */ - chunk->pages_used = 0; chunk->ndirty = 0; /* - * Initialize the map to contain one maximal free untouched - * run. + * Initialize the map to contain one maximal free untouched run. */ - memset(chunk->map, (CHUNK_MAP_LARGE | CHUNK_MAP_POS_MASK), - arena_chunk_header_npages); - memset(&chunk->map[arena_chunk_header_npages], - CHUNK_MAP_UNTOUCHED, (chunk_npages - - arena_chunk_header_npages)); - - /* Initialize the tree of unused extent nodes. */ - extent_tree_ad_new(&chunk->nodes); - chunk->nodes_past = (extent_node_t *)QUANTUM_CEILING( - (uintptr_t)&chunk->map[chunk_npages]); + for (i = 0; i < arena_chunk_header_npages; i++) + chunk->map[i].bits = 0; + chunk->map[i].bits = arena_maxclass | CHUNK_MAP_ZEROED; + for (i++; i < chunk_npages-1; i++) { + chunk->map[i].bits = CHUNK_MAP_ZEROED; + } + chunk->map[chunk_npages-1].bits = arena_maxclass | + CHUNK_MAP_ZEROED; } - /* Insert the run into the runs_avail_* red-black trees. */ - node = arena_chunk_node_alloc(chunk); - node->addr = (void *)((uintptr_t)chunk + (arena_chunk_header_npages << - pagesize_2pow)); - node->size = chunksize - (arena_chunk_header_npages << pagesize_2pow); - extent_tree_szad_insert(&arena->runs_avail_szad, node); - extent_tree_ad_insert(&arena->runs_avail_ad, node); + /* Insert the run into the runs_avail tree. */ + arena_avail_tree_insert(&arena->runs_avail, + &chunk->map[arena_chunk_header_npages]); return (chunk); } @@ -2358,11 +2357,8 @@ static void arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk) { - extent_node_t *node, key; if (arena->spare != NULL) { - arena_chunk_tree_all_remove(&chunk->arena->chunks_all, - arena->spare); if (arena->spare->ndirty > 0) { arena_chunk_tree_dirty_remove( &chunk->arena->chunks_dirty, arena->spare); @@ -2375,40 +2371,38 @@ } /* - * Remove run from the runs trees, regardless of whether this chunk + * Remove run from runs_avail, regardless of whether this chunk * will be cached, so that the arena does not use it. Dirty page * flushing only uses the chunks_dirty tree, so leaving this chunk in * the chunks_* trees is sufficient for that purpose. */ - key.addr = (void *)((uintptr_t)chunk + (arena_chunk_header_npages << - pagesize_2pow)); - node = extent_tree_ad_search(&arena->runs_avail_ad, &key); - assert(node != NULL); - extent_tree_szad_remove(&arena->runs_avail_szad, node); - extent_tree_ad_remove(&arena->runs_avail_ad, node); - arena_chunk_node_dealloc(chunk, node); + arena_avail_tree_remove(&arena->runs_avail, + &chunk->map[arena_chunk_header_npages]); arena->spare = chunk; } static arena_run_t * -arena_run_alloc(arena_t *arena, size_t size, bool small, bool zero) +arena_run_alloc(arena_t *arena, size_t size, bool large, bool zero) { arena_chunk_t *chunk; arena_run_t *run; - extent_node_t *node, key; + arena_chunk_map_t *mapelm, key; - assert(size <= (chunksize - (arena_chunk_header_npages << - pagesize_2pow))); + assert(size <= arena_maxclass); assert((size & pagesize_mask) == 0); /* Search the arena's chunks for the lowest best fit. */ - key.addr = NULL; - key.size = size; - node = extent_tree_szad_nsearch(&arena->runs_avail_szad, &key); - if (node != NULL) { - run = (arena_run_t *)node->addr; - arena_run_split(arena, run, size, small, zero); + key.bits = size | CHUNK_MAP_KEY; + mapelm = arena_avail_tree_nsearch(&arena->runs_avail, &key); + if (mapelm != NULL) { + arena_chunk_t *run_chunk = CHUNK_ADDR2BASE(mapelm); + size_t pageind = ((uintptr_t)mapelm - (uintptr_t)run_chunk->map) + / sizeof(arena_chunk_map_t); + + run = (arena_run_t *)((uintptr_t)run_chunk + (pageind + << pagesize_2pow)); + arena_run_split(arena, run, size, large, zero); return (run); } @@ -2421,7 +2415,7 @@ run = (arena_run_t *)((uintptr_t)chunk + (arena_chunk_header_npages << pagesize_2pow)); /* Update page map. */ - arena_run_split(arena, run, size, small, zero); + arena_run_split(arena, run, size, large, zero); return (run); } @@ -2431,15 +2425,8 @@ arena_chunk_t *chunk; size_t i, npages; #ifdef MALLOC_DEBUG - size_t ndirty; - - ndirty = 0; - rb_foreach_begin(arena_chunk_t, link_all, &arena->chunks_all, chunk) { - ndirty += chunk->ndirty; - } rb_foreach_end(arena_chunk_t, link_all, &arena->chunks_all, chunk) - assert(ndirty == arena->ndirty); + size_t ndirty = 0; - ndirty = 0; rb_foreach_begin(arena_chunk_t, link_dirty, &arena->chunks_dirty, chunk) { ndirty += chunk->ndirty; @@ -2465,22 +2452,20 @@ for (i = chunk_npages - 1; chunk->ndirty > 0; i--) { assert(i >= arena_chunk_header_npages); - if (chunk->map[i] & CHUNK_MAP_DIRTY) { - chunk->map[i] = (CHUNK_MAP_LARGE | - CHUNK_MAP_POS_MASK); + if (chunk->map[i].bits & CHUNK_MAP_DIRTY) { + chunk->map[i].bits ^= CHUNK_MAP_DIRTY; /* Find adjacent dirty run(s). */ for (npages = 1; i > arena_chunk_header_npages - && (chunk->map[i - 1] & CHUNK_MAP_DIRTY); - npages++) { + && (chunk->map[i - 1].bits & + CHUNK_MAP_DIRTY); npages++) { i--; - chunk->map[i] = (CHUNK_MAP_LARGE - | CHUNK_MAP_POS_MASK); + chunk->map[i].bits ^= CHUNK_MAP_DIRTY; } chunk->ndirty -= npages; arena->ndirty -= npages; madvise((void *)((uintptr_t)chunk + (i << - pagesize_2pow)), pagesize * npages, + pagesize_2pow)), (npages << pagesize_2pow), MADV_FREE); #ifdef MALLOC_STATS arena->stats.nmadvise++; @@ -2502,33 +2487,27 @@ arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty) { arena_chunk_t *chunk; - extent_node_t *nodeA, *nodeB, *nodeC, key; size_t size, run_ind, run_pages; - /* Remove run from runs_alloced_ad. */ - key.addr = run; - nodeB = extent_tree_ad_search(&arena->runs_alloced_ad, &key); - assert(nodeB != NULL); - extent_tree_ad_remove(&arena->runs_alloced_ad, nodeB); - size = nodeB->size; - chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run); - run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk) + run_ind = (size_t)(((uintptr_t)run - (uintptr_t)chunk) >> pagesize_2pow); assert(run_ind >= arena_chunk_header_npages); - assert(run_ind < (chunksize >> pagesize_2pow)); + assert(run_ind < chunk_npages); + if ((chunk->map[run_ind].bits & CHUNK_MAP_LARGE) != 0) + size = chunk->map[run_ind].bits & ~pagesize_mask; + else + size = run->bin->run_size; run_pages = (size >> pagesize_2pow); - /* Subtract pages from count of pages used in chunk. */ - chunk->pages_used -= run_pages; - + /* Mark pages as unallocated in the chunk map. */ if (dirty) { size_t i; for (i = 0; i < run_pages; i++) { - assert((chunk->map[run_ind + i] & CHUNK_MAP_DIRTY) == - 0); - chunk->map[run_ind + i] |= CHUNK_MAP_DIRTY; + assert((chunk->map[run_ind + i].bits & CHUNK_MAP_DIRTY) + == 0); + chunk->map[run_ind + i].bits = CHUNK_MAP_DIRTY; } if (chunk->ndirty == 0) { @@ -2537,64 +2516,74 @@ } chunk->ndirty += run_pages; arena->ndirty += run_pages; - } -#ifdef MALLOC_DEBUG - /* Set map elements to a bogus value in order to aid error detection. */ - { + } else { size_t i; for (i = 0; i < run_pages; i++) { - chunk->map[run_ind + i] |= (CHUNK_MAP_LARGE | - CHUNK_MAP_POS_MASK); + chunk->map[run_ind + i].bits &= ~(CHUNK_MAP_LARGE | + CHUNK_MAP_ALLOCATED); } } -#endif + chunk->map[run_ind].bits = size | (chunk->map[run_ind].bits & + pagesize_mask); + chunk->map[run_ind+run_pages-1].bits = size | + (chunk->map[run_ind+run_pages-1].bits & pagesize_mask); /* Try to coalesce forward. */ - key.addr = (void *)((uintptr_t)run + size); - nodeC = extent_tree_ad_nsearch(&arena->runs_avail_ad, &key); - if (nodeC != NULL && nodeC->addr == key.addr) { + if (run_ind + run_pages < chunk_npages && + (chunk->map[run_ind+run_pages].bits & CHUNK_MAP_ALLOCATED) == 0) { + size_t nrun_size = chunk->map[run_ind+run_pages].bits & + ~pagesize_mask; + /* - * Coalesce forward. This does not change the position within - * runs_avail_ad, so only remove/insert from/into - * runs_avail_szad. + * Remove successor from runs_avail; the coalesced run is + * inserted later. */ - extent_tree_szad_remove(&arena->runs_avail_szad, nodeC); - nodeC->addr = (void *)run; - nodeC->size += size; - extent_tree_szad_insert(&arena->runs_avail_szad, nodeC); - arena_chunk_node_dealloc(chunk, nodeB); - nodeB = nodeC; - } else { - /* - * Coalescing forward failed, so insert nodeB into runs_avail_*. - */ - extent_tree_szad_insert(&arena->runs_avail_szad, nodeB); - extent_tree_ad_insert(&arena->runs_avail_ad, nodeB); + arena_avail_tree_remove(&arena->runs_avail, + &chunk->map[run_ind+run_pages]); + + size += nrun_size; + run_pages = size >> pagesize_2pow; + + assert((chunk->map[run_ind+run_pages-1].bits & ~pagesize_mask) + == nrun_size); + chunk->map[run_ind].bits = size | (chunk->map[run_ind].bits & + pagesize_mask); + chunk->map[run_ind+run_pages-1].bits = size | + (chunk->map[run_ind+run_pages-1].bits & pagesize_mask); } /* Try to coalesce backward. */ - nodeA = extent_tree_ad_prev(&arena->runs_avail_ad, nodeB); - if (nodeA != NULL && (void *)((uintptr_t)nodeA->addr + nodeA->size) == - (void *)run) { + if (run_ind > arena_chunk_header_npages && (chunk->map[run_ind-1].bits & + CHUNK_MAP_ALLOCATED) == 0) { + size_t prun_size = chunk->map[run_ind-1].bits & ~pagesize_mask; + + run_ind -= prun_size >> pagesize_2pow; + /* - * Coalesce with previous run. This does not change nodeB's - * position within runs_avail_ad, so only remove/insert - * from/into runs_avail_szad. + * Remove predecessor from runs_avail; the coalesced run is + * inserted later. */ - extent_tree_szad_remove(&arena->runs_avail_szad, nodeA); - extent_tree_ad_remove(&arena->runs_avail_ad, nodeA); + arena_avail_tree_remove(&arena->runs_avail, + &chunk->map[run_ind]); - extent_tree_szad_remove(&arena->runs_avail_szad, nodeB); - nodeB->addr = nodeA->addr; - nodeB->size += nodeA->size; - extent_tree_szad_insert(&arena->runs_avail_szad, nodeB); + size += prun_size; + run_pages = size >> pagesize_2pow; - arena_chunk_node_dealloc(chunk, nodeA); + assert((chunk->map[run_ind].bits & ~pagesize_mask) == + prun_size); + chunk->map[run_ind].bits = size | (chunk->map[run_ind].bits & + pagesize_mask); + chunk->map[run_ind+run_pages-1].bits = size | + (chunk->map[run_ind+run_pages-1].bits & pagesize_mask); } + /* Insert into runs_avail, now that coalescing is complete. */ + arena_avail_tree_insert(&arena->runs_avail, &chunk->map[run_ind]); + /* Deallocate chunk if it is now completely unused. */ - if (chunk->pages_used == 0) + if ((chunk->map[arena_chunk_header_npages].bits & (~pagesize_mask | + CHUNK_MAP_ALLOCATED)) == arena_maxclass) arena_chunk_dealloc(arena, chunk); /* Enforce opt_dirty_max. */ @@ -2603,59 +2592,44 @@ } static void -arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk, extent_node_t *nodeB, - arena_run_t *run, size_t oldsize, size_t newsize) +arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, + size_t oldsize, size_t newsize) { - extent_node_t *nodeA; + size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> pagesize_2pow; + size_t head_npages = (oldsize - newsize) >> pagesize_2pow; - assert(nodeB->addr == run); - assert(nodeB->size == oldsize); assert(oldsize > newsize); /* - * Update the run's node in runs_alloced_ad. Its position does not - * change. + * Update the chunk map so that arena_run_dalloc() can treat the + * leading run as separately allocated. */ - nodeB->addr = (void *)((uintptr_t)run + (oldsize - newsize)); - nodeB->size = newsize; + chunk->map[pageind].bits = (oldsize - newsize) | CHUNK_MAP_LARGE | + CHUNK_MAP_ALLOCATED; + chunk->map[pageind+head_npages].bits = newsize | CHUNK_MAP_LARGE | + CHUNK_MAP_ALLOCATED; - /* - * Insert a node into runs_alloced_ad so that arena_run_dalloc() can - * treat the leading run as separately allocated. - */ - nodeA = arena_chunk_node_alloc(chunk); - nodeA->addr = (void *)run; - nodeA->size = oldsize - newsize; - extent_tree_ad_insert(&arena->runs_alloced_ad, nodeA); - - arena_run_dalloc(arena, (arena_run_t *)run, false); + arena_run_dalloc(arena, run, false); } static void -arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk, extent_node_t *nodeA, - arena_run_t *run, size_t oldsize, size_t newsize, bool dirty) +arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run, + size_t oldsize, size_t newsize, bool dirty) { - extent_node_t *nodeB; + size_t pageind = ((uintptr_t)run - (uintptr_t)chunk) >> pagesize_2pow; + size_t npages = newsize >> pagesize_2pow; - assert(nodeA->addr == run); - assert(nodeA->size == oldsize); assert(oldsize > newsize); /* >>> TRUNCATED FOR MAIL (1000 lines) <<<
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200808200824.m7K8OnfI021838>