From 606579063153888ea1aa1339ce0f1ed8afc12744 Mon Sep 17 00:00:00 2001 From: Ariane van der Steldt Date: Wed, 11 Apr 2012 11:23:23 +0000 Subject: vmmap: speed up allocations Reduces O(n log n) allocations to O(log n). ok deraadt, tedu --- sys/uvm/uvm_addr.c | 101 +++++++++++++++++++++------------------------ sys/uvm/uvm_map.c | 118 +++++++++++++++++++++++++++++++++++------------------ sys/uvm/uvm_map.h | 4 +- 3 files changed, 128 insertions(+), 95 deletions(-) diff --git a/sys/uvm/uvm_addr.c b/sys/uvm/uvm_addr.c index ccf4f16430e..82c10a350a5 100644 --- a/sys/uvm/uvm_addr.c +++ b/sys/uvm/uvm_addr.c @@ -1,4 +1,4 @@ -/* $OpenBSD: uvm_addr.c,v 1.2 2012/03/15 17:52:28 ariane Exp $ */ +/* $OpenBSD: uvm_addr.c,v 1.3 2012/04/11 11:23:22 ariane Exp $ */ /* * Copyright (c) 2011 Ariane van der Steldt @@ -571,7 +571,7 @@ uaddr_rnd_select(struct vm_map *map, struct uvm_addr_state *uaddr, struct vmspace *vm; vaddr_t guard_sz; vaddr_t low_addr, high_addr; - struct vm_map_entry *entry; + struct vm_map_entry *entry, *next; vsize_t before_gap, after_gap; vaddr_t tmp; @@ -601,40 +601,61 @@ uaddr_rnd_select(struct vm_map *map, struct uvm_addr_state *uaddr, before_gap = 0; after_gap = guard_sz; + hint -= MIN(hint, before_gap); /* - * Find the first entry at or after hint with free space. + * Use the augmented address tree to look up the first entry + * at or after hint with sufficient space. + * + * This code is the original optimized code, but will fail if the + * subtree it looks at does have sufficient space, but fails to meet + * the align constraint. * - * Since we need an entry that is on the free-list, search until - * we hit an entry that is owned by our uaddr. + * Guard: subtree is not exhausted and max(fspace) >= required. */ - for (entry = uvm_map_entrybyaddr(&map->addr, hint); - entry != NULL && - uvm_map_uaddr_e(map, entry) != uaddr; - entry = RB_NEXT(uvm_map_addr, &map->addr, entry)) { - /* Fail if we search past uaddr_maxaddr. */ - if (VMMAP_FREE_START(entry) >= uaddr->uaddr_maxaddr) { - entry = NULL; - break; - } - } + entry = uvm_map_entrybyaddr(&map->addr, hint); - for ( /* initial entry filled in above */ ; - entry != NULL && VMMAP_FREE_START(entry) < uaddr->uaddr_maxaddr; - entry = TAILQ_NEXT(entry, dfree.tailq)) { - if (uvm_addr_fitspace(&low_addr, &high_addr, + /* Walk up the tree, until there is at least sufficient space. */ + while (entry != NULL && + entry->fspace_augment < before_gap + after_gap + sz) + entry = RB_PARENT(entry, daddrs.addr_entry); + + while (entry != NULL) { + /* Test if this fits. */ + if (VMMAP_FREE_END(entry) > hint && + uvm_map_uaddr_e(map, entry) == uaddr && + uvm_addr_fitspace(&low_addr, &high_addr, MAX(uaddr->uaddr_minaddr, VMMAP_FREE_START(entry)), MIN(uaddr->uaddr_maxaddr, VMMAP_FREE_END(entry)), sz, align, offset, before_gap, after_gap) == 0) { *entry_out = entry; - if (hint >= low_addr && hint <= high_addr) - *addr_out = hint; - else - *addr_out = low_addr; + *addr_out = low_addr; return 0; } + + /* RB_NEXT, but skip subtrees that cannot possible fit. */ + next = RB_RIGHT(entry, daddrs.addr_entry); + if (next != NULL && + next->fspace_augment >= before_gap + after_gap + sz) { + entry = next; + while ((next = RB_LEFT(entry, daddrs.addr_entry)) != + NULL) + entry = next; + } else { +do_parent: + next = RB_PARENT(entry, daddrs.addr_entry); + if (next == NULL) + entry = NULL; + else if (RB_LEFT(next, daddrs.addr_entry) == entry) + entry = next; + else { + entry = next; + goto do_parent; + } + } } + /* Lookup failed. */ return ENOMEM; } @@ -654,34 +675,7 @@ void uaddr_rnd_insert(struct vm_map *map, struct uvm_addr_state *uaddr_p, struct vm_map_entry *entry) { - struct uaddr_rnd_state *uaddr; - struct vm_map_entry *prev; - - uaddr = (struct uaddr_rnd_state*)uaddr_p; - KASSERT(entry == RB_FIND(uvm_map_addr, &map->addr, entry)); - - /* - * Make prev the first vm_map_entry before entry. - */ - for (prev = RB_PREV(uvm_map_addr, &map->addr, entry); - prev != NULL; - prev = RB_PREV(uvm_map_addr, &map->addr, prev)) { - /* Stop and fail when reaching uaddr minaddr. */ - if (VMMAP_FREE_START(prev) < uaddr_p->uaddr_minaddr) { - prev = NULL; - break; - } - - KASSERT(prev->etype & UVM_ET_FREEMAPPED); - if (uvm_map_uaddr_e(map, prev) == uaddr_p) - break; - } - - /* Perform insertion. */ - if (prev == NULL) - TAILQ_INSERT_HEAD(&uaddr->ur_free, entry, dfree.tailq); - else - TAILQ_INSERT_AFTER(&uaddr->ur_free, prev, entry, dfree.tailq); + return; } /* @@ -691,10 +685,7 @@ void uaddr_rnd_remove(struct vm_map *map, struct uvm_addr_state *uaddr_p, struct vm_map_entry *entry) { - struct uaddr_rnd_state *uaddr; - - uaddr = (struct uaddr_rnd_state*)uaddr_p; - TAILQ_REMOVE(&uaddr->ur_free, entry, dfree.tailq); + return; } #if defined(DEBUG) || defined(DDB) diff --git a/sys/uvm/uvm_map.c b/sys/uvm/uvm_map.c index 1b8cc197e77..8d96b1c0089 100644 --- a/sys/uvm/uvm_map.c +++ b/sys/uvm/uvm_map.c @@ -1,4 +1,4 @@ -/* $OpenBSD: uvm_map.c,v 1.150 2012/03/15 22:22:28 ariane Exp $ */ +/* $OpenBSD: uvm_map.c,v 1.151 2012/04/11 11:23:22 ariane Exp $ */ /* $NetBSD: uvm_map.c,v 1.86 2000/11/27 08:40:03 chs Exp $ */ /* @@ -157,6 +157,8 @@ int uvm_map_findspace(struct vm_map*, struct vm_map_entry**, struct vm_map_entry**, vaddr_t*, vsize_t, vaddr_t, vaddr_t, vm_prot_t, vaddr_t); +vsize_t uvm_map_addr_augment_get(struct vm_map_entry*); +void uvm_map_addr_augment(struct vm_map_entry*); /* * Tree management functions. @@ -405,11 +407,16 @@ uvm_mapent_free_insert(struct vm_map *map, struct uvm_addr_state *uaddr, UVM_MAP_REQ_WRITE(map); /* Actual insert: forward to uaddr pointer. */ - fun = uaddr->uaddr_functions; - KDASSERT(fun != NULL); - if (fun->uaddr_free_insert != NULL) - (*fun->uaddr_free_insert)(map, uaddr, entry); - entry->etype |= UVM_ET_FREEMAPPED; + if (uaddr != NULL) { + fun = uaddr->uaddr_functions; + KDASSERT(fun != NULL); + if (fun->uaddr_free_insert != NULL) + (*fun->uaddr_free_insert)(map, uaddr, entry); + entry->etype |= UVM_ET_FREEMAPPED; + } + + /* Update fspace augmentation. */ + uvm_map_addr_augment(entry); } /* @@ -421,14 +428,16 @@ uvm_mapent_free_remove(struct vm_map *map, struct uvm_addr_state *uaddr, { const struct uvm_addr_functions *fun; - KASSERT((entry->etype & UVM_ET_FREEMAPPED) != 0); + KASSERT((entry->etype & UVM_ET_FREEMAPPED) != 0 || uaddr == NULL); KASSERT(uvm_map_uaddr_e(map, entry) == uaddr); UVM_MAP_REQ_WRITE(map); - fun = uaddr->uaddr_functions; - if (fun->uaddr_free_remove != NULL) - (*fun->uaddr_free_remove)(map, uaddr, entry); - entry->etype &= ~UVM_ET_FREEMAPPED; + if (uaddr != NULL) { + fun = uaddr->uaddr_functions; + if (fun->uaddr_free_remove != NULL) + (*fun->uaddr_free_remove)(map, uaddr, entry); + entry->etype &= ~UVM_ET_FREEMAPPED; + } } /* @@ -889,6 +898,46 @@ uvm_map_findspace(struct vm_map *map, struct vm_map_entry**first, return ENOMEM; } +/* Calculate entry augmentation value. */ +vsize_t +uvm_map_addr_augment_get(struct vm_map_entry *entry) +{ + vsize_t augment; + struct vm_map_entry *left, *right; + + augment = entry->fspace; + if ((left = RB_LEFT(entry, daddrs.addr_entry)) != NULL) + augment = MAX(augment, left->fspace_augment); + if ((right = RB_RIGHT(entry, daddrs.addr_entry)) != NULL) + augment = MAX(augment, right->fspace_augment); + return augment; +} + +/* + * Update augmentation data in entry. + */ +void +uvm_map_addr_augment(struct vm_map_entry *entry) +{ + vsize_t augment; + + while (entry != NULL) { + /* Calculate value for augmentation. */ + augment = uvm_map_addr_augment_get(entry); + + /* + * Descend update. + * Once we find an entry that already has the correct value, + * stop, since it means all its parents will use the correct + * value too. + */ + if (entry->fspace_augment == augment) + return; + entry->fspace_augment = augment; + entry = RB_PARENT(entry, daddrs.addr_entry); + } +} + /* * uvm_map: establish a valid mapping in map * @@ -1254,18 +1303,15 @@ uvm_mapent_merge(struct vm_map *map, struct vm_map_entry *e1, */ free = uvm_map_uaddr_e(map, e1); - if (free) - uvm_mapent_free_remove(map, free, e1); + uvm_mapent_free_remove(map, free, e1); free = uvm_map_uaddr_e(map, e2); - if (free) - uvm_mapent_free_remove(map, free, e2); + uvm_mapent_free_remove(map, free, e2); uvm_mapent_addr_remove(map, e2); e1->end = e2->end; e1->guard = e2->guard; e1->fspace = e2->fspace; - if (free) - uvm_mapent_free_insert(map, free, e1); + uvm_mapent_free_insert(map, free, e1); DEAD_ENTRY_PUSH(dead, e2); return e1; @@ -1402,8 +1448,7 @@ uvm_map_mkentry(struct vm_map *map, struct vm_map_entry *first, * Reset free space in first. */ free = uvm_map_uaddr_e(map, first); - if (free) - uvm_mapent_free_remove(map, free, first); + uvm_mapent_free_remove(map, free, first); first->guard = 0; first->fspace = 0; @@ -1416,8 +1461,7 @@ uvm_map_mkentry(struct vm_map *map, struct vm_map_entry *first, KDASSERT(last->start == last->end); free = uvm_map_uaddr_e(map, last); - if (free) - uvm_mapent_free_remove(map, free, last); + uvm_mapent_free_remove(map, free, last); uvm_mapent_addr_remove(map, last); DEAD_ENTRY_PUSH(dead, last); } @@ -1639,16 +1683,14 @@ uvm_mapent_mkfree(struct vm_map *map, struct vm_map_entry *entry, addr = entry->start; end = VMMAP_FREE_END(entry); free = uvm_map_uaddr_e(map, entry); - if (free) - uvm_mapent_free_remove(map, free, entry); + uvm_mapent_free_remove(map, free, entry); uvm_mapent_addr_remove(map, entry); DEAD_ENTRY_PUSH(dead, entry); if (markfree) { if (prev) { free = uvm_map_uaddr_e(map, prev); - if (free) - uvm_mapent_free_remove(map, free, prev); + uvm_mapent_free_remove(map, free, prev); } *prev_ptr = uvm_map_fix_space(map, prev, addr, end, 0); } @@ -2372,8 +2414,7 @@ uvm_map_splitentry(struct vm_map *map, struct vm_map_entry *orig, * Free space will change, unlink from free space tree. */ free = uvm_map_uaddr_e(map, orig); - if (free) - uvm_mapent_free_remove(map, free, orig); + uvm_mapent_free_remove(map, free, orig); adj = split - orig->start; @@ -2421,11 +2462,9 @@ uvm_map_splitentry(struct vm_map *map, struct vm_map_entry *orig, free_before = free; else free_before = uvm_map_uaddr_e(map, orig); - if (free_before) - uvm_mapent_free_insert(map, free_before, orig); + uvm_mapent_free_insert(map, free_before, orig); uvm_mapent_addr_insert(map, next); - if (free) - uvm_mapent_free_insert(map, free, next); + uvm_mapent_free_insert(map, free, next); uvm_tree_sanity(map, __FILE__, __LINE__); } @@ -2709,6 +2748,7 @@ uvm_map_printit(struct vm_map *map, boolean_t full, in_free ? 'T' : 'F', entry->guard, VMMAP_FREE_START(entry), VMMAP_FREE_END(entry)); + (*pr)("\tfspace_augment=%lu\n", entry->fspace_augment); (*pr)("\tfreemapped=%c, uaddr=%p\n", (entry->etype & UVM_ET_FREEMAPPED) ? 'T' : 'F', free); if (free) { @@ -4232,8 +4272,7 @@ uvm_map_clip_start(struct vm_map *map, struct vm_map_entry *entry, vaddr_t addr) /* Unlink original. */ free = uvm_map_uaddr_e(map, entry); - if (free) - uvm_mapent_free_remove(map, free, entry); + uvm_mapent_free_remove(map, free, entry); uvm_mapent_addr_remove(map, entry); /* Copy entry. */ @@ -4243,8 +4282,7 @@ uvm_map_clip_start(struct vm_map *map, struct vm_map_entry *entry, vaddr_t addr) /* Put new entry in place of original entry. */ uvm_mapent_addr_insert(map, tmp); - if (free) - uvm_mapent_free_insert(map, free, tmp); + uvm_mapent_free_insert(map, free, tmp); /* Invoke splitentry. */ uvm_map_splitentry(map, tmp, entry, addr); @@ -4502,8 +4540,7 @@ uvm_map_freelist_update_clear(struct vm_map *map, struct uvm_map_deadq *dead) next = RB_NEXT(uvm_map_addr, &map->addr, entry); free = uvm_map_uaddr_e(map, entry); - if (free) - uvm_mapent_free_remove(map, free, entry); + uvm_mapent_free_remove(map, free, entry); if (prev != NULL && entry->start == entry->end) { prev->fspace += VMMAP_FREE_END(entry) - entry->end; @@ -4664,7 +4701,7 @@ uvm_map_fix_space(struct vm_map *map, struct vm_map_entry *entry, * We'll start a new entry and add to that entry * instead. */ - if (entry != NULL && entfree != NULL) + if (entry != NULL) uvm_mapent_free_insert(map, entfree, entry); /* New entry for new uaddr. */ @@ -4690,7 +4727,7 @@ uvm_map_fix_space(struct vm_map *map, struct vm_map_entry *entry, min = lmax; } /* Finally put entry on the uaddr state. */ - if (entry != NULL && entfree != NULL) + if (entry != NULL) uvm_mapent_free_insert(map, entfree, entry); return entry; @@ -4983,8 +5020,11 @@ vm_map_unbusy_ln(struct vm_map *map, char *file, int line) } +#undef RB_AUGMENT +#define RB_AUGMENT(x) uvm_map_addr_augment((x)) RB_GENERATE(uvm_map_addr, vm_map_entry, daddrs.addr_entry, uvm_mapentry_addrcmp); +#undef RB_AUGMENT /* diff --git a/sys/uvm/uvm_map.h b/sys/uvm/uvm_map.h index e0e21267e31..9cf6827b609 100644 --- a/sys/uvm/uvm_map.h +++ b/sys/uvm/uvm_map.h @@ -1,4 +1,4 @@ -/* $OpenBSD: uvm_map.h,v 1.47 2012/03/09 13:01:29 ariane Exp $ */ +/* $OpenBSD: uvm_map.h,v 1.48 2012/04/11 11:23:22 ariane Exp $ */ /* $NetBSD: uvm_map.h,v 1.24 2001/02/18 21:19:08 chs Exp $ */ /* @@ -197,6 +197,8 @@ struct vm_map_entry { #define UVM_MAP_STATIC 0x01 /* static map entry */ #define UVM_MAP_KMEM 0x02 /* from kmem entry pool */ + + vsize_t fspace_augment; /* max(fspace) in subtree */ }; #define VM_MAPENT_ISWIRED(entry) ((entry)->wired_count != 0) -- cgit v1.2.3