From 1db202eb8406785500f1bc3ceef7868566e416a1 Mon Sep 17 00:00:00 2001 From: Richard Braun Date: Fri, 20 May 2016 20:10:52 +0200 Subject: vm_map: back allocations with a red-black tree This change augments VM maps with a gap tree, sorted by gap size, to use for non-fixed allocations. * vm/vm_map.c: Include kern/list.h. (vm_map_entry_gap_cmp_lookup, vm_map_entry_gap_cmp_insert, vm_map_gap_valid, vm_map_gap_compute, vm_map_gap_insert_single, vm_map_gap_remove_single, vm_map_gap_update, vm_map_gap_insert, vm_map_gap_remove, vm_map_find_entry_anywhere): New functions. (vm_map_setup): Initialize gap tree. (_vm_map_entry_link): Call vm_map_gap_insert. (_vm_map_entry_unlink): Call vm_map_gap_remove. (vm_map_find_entry, vm_map_enter, vm_map_copyout, vm_map_copyout_page_list, vm_map_copyin): Replace look up loop with a call to vm_map_find_entry_anywhere. Call vm_map_gap_update and initialize gap tree where relevant. (vm_map_copy_insert): Turn macro into an inline function and rewrite. (vm_map_simplify): Reorder call to vm_map_entry_unlink so that previous entry is suitable for use with gap management functions. * vm/vm_map.h: Include kern/list.h. (struct vm_map_entry): New members `gap_node`, `gap_list`, `gap_size` and `in_gap_tree`. (struct vm_map_header): New member `gap_tree`. --- vm/vm_map.h | 11 +++++++++++ 1 file changed, 11 insertions(+) (limited to 'vm/vm_map.h') diff --git a/vm/vm_map.h b/vm/vm_map.h index b4ba7c7b..74c86a79 100644 --- a/vm/vm_map.h +++ b/vm/vm_map.h @@ -50,6 +50,7 @@ #include #include #include +#include #include #include #include @@ -105,9 +106,17 @@ struct vm_map_entry { #define vme_start links.start #define vme_end links.end struct rbtree_node tree_node; /* links to other entries in tree */ + struct rbtree_node gap_node; /* links to other entries in gap tree */ + struct list gap_list; /* links to other entries with + the same gap size */ + vm_size_t gap_size; /* size of available memory + following this entry */ union vm_map_object object; /* object I point to */ vm_offset_t offset; /* offset into object */ unsigned int + /* boolean_t */ in_gap_tree:1, /* entry is in the gap tree if true, + or linked to other entries with + the same gap size if false */ /* boolean_t */ is_shared:1, /* region is shared */ /* boolean_t */ is_sub_map:1, /* Is "object" a submap? */ /* boolean_t */ in_transition:1, /* Entry being changed */ @@ -141,6 +150,8 @@ typedef struct vm_map_entry *vm_map_entry_t; struct vm_map_header { struct vm_map_links links; /* first, last, min, max */ struct rbtree tree; /* Sorted tree of entries */ + struct rbtree gap_tree; /* Sorted tree of gap lists + for allocations */ int nentries; /* Number of entries */ boolean_t entries_pageable; /* are map entries pageable? */ -- cgit v1.2.3