|
[ source navigation ] [ diff markup ] [ identifier search ] [ general search ] |
|||
|
001 /* Copyright (C) 2000 Thomas Petazzoni 001 /* Copyright (C) 2000 Thomas Petazzoni 002 Copyright (C) 2004 David Decotigny 002 Copyright (C) 2004 David Decotigny 003 003 004 This program is free software; you can redi 004 This program is free software; you can redistribute it and/or 005 modify it under the terms of the GNU Genera 005 modify it under the terms of the GNU General Public License 006 as published by the Free Software Foundatio 006 as published by the Free Software Foundation; either version 2 007 of the License, or (at your option) any lat 007 of the License, or (at your option) any later version. 008 008 009 This program is distributed in the hope tha 009 This program is distributed in the hope that it will be useful, 010 but WITHOUT ANY WARRANTY; without even the 010 but WITHOUT ANY WARRANTY; without even the implied warranty of 011 MERCHANTABILITY or FITNESS FOR A PARTICULAR 011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 012 GNU General Public License for more details 012 GNU General Public License for more details. 013 013 014 You should have received a copy of the GNU 014 You should have received a copy of the GNU General Public License 015 along with this program; if not, write to t 015 along with this program; if not, write to the Free Software 016 Foundation, Inc., 59 Temple Place - Suite 3 016 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 017 USA. 017 USA. 018 */ 018 */ 019 #ifndef _SOS_KMEM_SLAB_H_ 019 #ifndef _SOS_KMEM_SLAB_H_ 020 #define _SOS_KMEM_SLAB_H_ 020 #define _SOS_KMEM_SLAB_H_ 021 021 022 /** 022 /** 023 * @file kmem_slab.h 023 * @file kmem_slab.h 024 * 024 * 025 * Kernel Memory Allocator based on Bonwick's 025 * Kernel Memory Allocator based on Bonwick's slab llocator (Solaris 026 * 2.4, Linux 2.4). This allocator achieves go 026 * 2.4, Linux 2.4). This allocator achieves good memory utilization 027 * ratio (memory effectively used / memory req 027 * ratio (memory effectively used / memory requested) ie limited 028 * fragmentation, while elegantly handling cac 028 * fragmentation, while elegantly handling cache-effect considerations 029 * (TLB locality through the notion of "cache" 029 * (TLB locality through the notion of "cache" of slabs, and the 030 * dcache utilization through the notion of ca 030 * dcache utilization through the notion of cache colouring to 031 * decrease the conflicts in the dcache for ac 031 * decrease the conflicts in the dcache for accesses to different data 032 * in the same cache). 032 * in the same cache). 033 * 033 * 034 * This allocator relies on the range allocato 034 * This allocator relies on the range allocator (kmem_vmm.h) to 035 * allocate the slabs, which itself relies on 035 * allocate the slabs, which itself relies on the slab allocator to 036 * allocate its "range" data structures, thus 036 * allocate its "range" data structures, thus leading to a 037 * chicken-and-egg problem. We solve this prob 037 * chicken-and-egg problem. We solve this problem by introducing the 038 * notion of "min_free_objs" for the slab cach 038 * notion of "min_free_objs" for the slab caches, in order for the cache 039 * of ranges to always have enough ranges in r 039 * of ranges to always have enough ranges in reserve to complete the 040 * range allocation before being urged to allo 040 * range allocation before being urged to allocate a new slab of 041 * ranges, which would require the allocation 041 * ranges, which would require the allocation of a new range. 042 * 042 * 043 * Compared to Bonwick's recommendations, we d 043 * Compared to Bonwick's recommendations, we don't handle ctor/dtor 044 * routines on the objects, so that we can alt 044 * routines on the objects, so that we can alter the objects once they 045 * are set free. Thus, the list of free object 045 * are set free. Thus, the list of free object is stored in the free 046 * objects themselves, not alongside the objec 046 * objects themselves, not alongside the objects (this also implies that 047 * the SOS_KSLAB_CREATE_MAP flag below is mean 047 * the SOS_KSLAB_CREATE_MAP flag below is meaningless). We also don't 048 * implement the cache colouring (trivial to a 048 * implement the cache colouring (trivial to add, but we omit it for 049 * readability reasons), and the only alignmen 049 * readability reasons), and the only alignment constraint we respect 050 * is that allocated objects are aligned on a 050 * is that allocated objects are aligned on a 4B boundary: for other 051 * alignment constraints, the user must integr 051 * alignment constraints, the user must integrate them in the 052 * "object_size" parameter to "sos_kmem_cache_ 052 * "object_size" parameter to "sos_kmem_cache_create()". 053 * 053 * 054 * References : 054 * References : 055 * - J. Bonwick's paper, "The slab allocator: 055 * - J. Bonwick's paper, "The slab allocator: An object-caching kernel 056 * memory allocator", In USENIX Summer 1994 056 * memory allocator", In USENIX Summer 1994 Technical Conference 057 * - The bible, aka "Unix internals : the new 057 * - The bible, aka "Unix internals : the new frontiers" (section 058 * 12.10), Uresh Vahalia, Prentice Hall 1996 058 * 12.10), Uresh Vahalia, Prentice Hall 1996, ISBN 0131019082 059 * - "The Linux slab allocator", B. Fitzgibbon 059 * - "The Linux slab allocator", B. Fitzgibbons, 060 * http://www.cc.gatech.edu/people/home/brad 060 * http://www.cc.gatech.edu/people/home/bradf/cs7001/proj2/ 061 * - The Kos, http://kos.enix.org/ 061 * - The Kos, http://kos.enix.org/ 062 */ 062 */ 063 #include <sos/types.h> 063 #include <sos/types.h> 064 #include <sos/errno.h> 064 #include <sos/errno.h> 065 065 066 /** Opaque data structure that defines a Cache 066 /** Opaque data structure that defines a Cache of slabs */ 067 struct sos_kslab_cache; 067 struct sos_kslab_cache; 068 068 069 /** Opaque data structure that defines a slab. 069 /** Opaque data structure that defines a slab. Exported only to 070 kmem_vmm.h */ 070 kmem_vmm.h */ 071 struct sos_kslab; 071 struct sos_kslab; 072 072 073 #include "kmem_vmm.h" 073 #include "kmem_vmm.h" 074 074 075 075 076 /** The maximum allowed pages for each slab * 076 /** The maximum allowed pages for each slab */ 077 #define MAX_PAGES_PER_SLAB 32 /* 128 kB */ 077 #define MAX_PAGES_PER_SLAB 32 /* 128 kB */ 078 078 079 079 080 /** 080 /** 081 * Initialize the slab cache of slab caches, a 081 * Initialize the slab cache of slab caches, and prepare the cache of 082 * kmem_range for kmem_vmm. 082 * kmem_range for kmem_vmm. 083 * 083 * 084 * @param kernel_core_base The virtual address 084 * @param kernel_core_base The virtual address of the first byte used 085 * by the kernel code/data 085 * by the kernel code/data 086 * 086 * 087 * @param kernel_core_top The virtual address 087 * @param kernel_core_top The virtual address of the first byte after 088 * the kernel code/data. 088 * the kernel code/data. 089 * 089 * 090 * @param sizeof_struct_range the size of the 090 * @param sizeof_struct_range the size of the objects (aka "struct 091 * sos_kmem_vmm_ranges") to be allocated in th 091 * sos_kmem_vmm_ranges") to be allocated in the cache of ranges 092 * 092 * 093 * @param first_struct_slab_of_caches (output 093 * @param first_struct_slab_of_caches (output value) the virtual 094 * address of the first slab structure that ge 094 * address of the first slab structure that gets allocated for the 095 * cache of caches. The function actually manu 095 * cache of caches. The function actually manually allocate the first 096 * slab of the cache of caches because of a ch 096 * slab of the cache of caches because of a chicken-and-egg thing. The 097 * address of the slab is used by the kmem_vmm 097 * address of the slab is used by the kmem_vmm_setup routine to 098 * finalize the allocation of the slab, in ord 098 * finalize the allocation of the slab, in order for it to behave like 099 * a real slab afterwards. 099 * a real slab afterwards. 100 * 100 * 101 * @param first_slab_of_caches_base (output va 101 * @param first_slab_of_caches_base (output value) the virtual address 102 * of the slab associated to the slab structur 102 * of the slab associated to the slab structure. 103 * 103 * 104 * @param first_slab_of_caches_nb_pages (outpu 104 * @param first_slab_of_caches_nb_pages (output value) the number of 105 * (virtual) pages used by the first slab of t 105 * (virtual) pages used by the first slab of the cache of caches. 106 * 106 * 107 * @param first_struct_slab_of_ranges (output 107 * @param first_struct_slab_of_ranges (output value) the virtual address 108 * of the first slab that gets allocated for t 108 * of the first slab that gets allocated for the cache of ranges. Same 109 * explanation as above. 109 * explanation as above. 110 * 110 * 111 * @param first_slab_of_ranges_base (output va 111 * @param first_slab_of_ranges_base (output value) the virtual address 112 * of the slab associated to the slab structur 112 * of the slab associated to the slab structure. 113 * 113 * 114 * @param first_slab_of_ranges_nb_pages (outpu 114 * @param first_slab_of_ranges_nb_pages (output value) the number of 115 * (virtual) pages used by the first slab of t 115 * (virtual) pages used by the first slab of the cache of ranges. 116 * 116 * 117 * @return the cache of kmem_range immediatly 117 * @return the cache of kmem_range immediatly usable 118 */ 118 */ 119 struct sos_kslab_cache * 119 struct sos_kslab_cache * 120 sos_kmem_cache_setup_prepare(sos_vaddr_t kerne !! 120 sos_kmem_cache_subsystem_setup_prepare(sos_vaddr_t kernel_core_base, 121 sos_vaddr_t kerne !! 121 sos_vaddr_t kernel_core_top, 122 sos_size_t sizeo !! 122 sos_size_t sizeof_struct_range, 123 /* results */ !! 123 /* results */ 124 struct sos_kslab !! 124 struct sos_kslab **first_struct_slab_of_caches, 125 sos_vaddr_t *firs !! 125 sos_vaddr_t *first_slab_of_caches_base, 126 sos_count_t *firs !! 126 sos_count_t *first_slab_of_caches_nb_pages, 127 struct sos_kslab !! 127 struct sos_kslab **first_struct_slab_of_ranges, 128 sos_vaddr_t *firs !! 128 sos_vaddr_t *first_slab_of_ranges_base, 129 sos_count_t *firs !! 129 sos_count_t *first_slab_of_ranges_nb_pages); 130 130 131 /** 131 /** 132 * Update the configuration of the cache subsy 132 * Update the configuration of the cache subsystem once the vmm 133 * subsystem has been fully initialized 133 * subsystem has been fully initialized 134 */ 134 */ 135 sos_ret_t 135 sos_ret_t 136 sos_kmem_cache_setup_commit(struct sos_kslab * !! 136 sos_kmem_cache_subsystem_setup_commit(struct sos_kslab *first_struct_slab_of_caches, 137 struct sos_kmem_ra !! 137 struct sos_kmem_range *first_range_of_caches, 138 struct sos_kslab * !! 138 struct sos_kslab *first_struct_slab_of_ranges, 139 struct sos_kmem_ra !! 139 struct sos_kmem_range *first_range_of_ranges); 140 140 141 141 142 /* 142 /* 143 * Flags for sos_kmem_cache_create() 143 * Flags for sos_kmem_cache_create() 144 */ 144 */ 145 /** The slabs should be initially mapped in ph 145 /** The slabs should be initially mapped in physical memory */ 146 #define SOS_KSLAB_CREATE_MAP (1<<0) 146 #define SOS_KSLAB_CREATE_MAP (1<<0) 147 /** The object should always be set to zero at 147 /** The object should always be set to zero at allocation (implies 148 SOS_KSLAB_CREATE_MAP) */ 148 SOS_KSLAB_CREATE_MAP) */ 149 #define SOS_KSLAB_CREATE_ZERO (1<<1) 149 #define SOS_KSLAB_CREATE_ZERO (1<<1) 150 150 151 /** 151 /** 152 * @note this function MAY block (involved all 152 * @note this function MAY block (involved allocations are not atomic) 153 * @param name must remain valid during the wh 153 * @param name must remain valid during the whole cache's life 154 * (shallow copy) ! 154 * (shallow copy) ! 155 * @param cache_flags An or-ed combination of 155 * @param cache_flags An or-ed combination of the SOS_KSLAB_CREATE_* flags 156 */ 156 */ 157 struct sos_kslab_cache * 157 struct sos_kslab_cache * 158 sos_kmem_cache_create(const char* name, 158 sos_kmem_cache_create(const char* name, 159 sos_size_t object_size, 159 sos_size_t object_size, 160 sos_count_t pages_per_sl 160 sos_count_t pages_per_slab, 161 sos_count_t min_free_obj 161 sos_count_t min_free_objects, 162 sos_ui32_t cache_flags) 162 sos_ui32_t cache_flags); 163 163 164 sos_ret_t sos_kmem_cache_destroy(struct sos_ks 164 sos_ret_t sos_kmem_cache_destroy(struct sos_kslab_cache *kslab_cache); 165 165 166 166 167 /* 167 /* 168 * Flags for sos_kmem_cache_alloc() 168 * Flags for sos_kmem_cache_alloc() 169 */ 169 */ 170 /** Allocation should either succeed or fail, 170 /** Allocation should either succeed or fail, without blocking */ 171 #define SOS_KSLAB_ALLOC_ATOMIC (1<<0) 171 #define SOS_KSLAB_ALLOC_ATOMIC (1<<0) 172 172 173 /** 173 /** 174 * Allocate an object from the given cache. 174 * Allocate an object from the given cache. 175 * 175 * 176 * @param alloc_flags An or-ed combination of 176 * @param alloc_flags An or-ed combination of the SOS_KSLAB_ALLOC_* flags 177 */ 177 */ 178 sos_vaddr_t sos_kmem_cache_alloc(struct sos_ks 178 sos_vaddr_t sos_kmem_cache_alloc(struct sos_kslab_cache *kslab_cache, 179 sos_ui32_t al 179 sos_ui32_t alloc_flags); 180 180 181 181 182 /** 182 /** 183 * Free an object (assumed to be already alloc 183 * Free an object (assumed to be already allocated and not already 184 * free) at the given virtual address. 184 * free) at the given virtual address. 185 */ 185 */ 186 sos_ret_t sos_kmem_cache_free(sos_vaddr_t vadd 186 sos_ret_t sos_kmem_cache_free(sos_vaddr_t vaddr); 187 187 188 188 189 /* 189 /* 190 * Function reserved to kmem_vmm.c. Does almos 190 * Function reserved to kmem_vmm.c. Does almost everything 191 * sos_kmem_cache_free() does, except it does 191 * sos_kmem_cache_free() does, except it does not call 192 * sos_kmem_vmm_del_range() if it needs to. Th 192 * sos_kmem_vmm_del_range() if it needs to. This is aimed at avoiding 193 * large recursion when a range is freed with 193 * large recursion when a range is freed with 194 * sos_kmem_vmm_del_range(). 194 * sos_kmem_vmm_del_range(). 195 * 195 * 196 * @param the_range The range structure to fre 196 * @param the_range The range structure to free 197 * 197 * 198 * @return NULL when the range containing 'the 198 * @return NULL when the range containing 'the_range' still contains 199 * other ranges, or the address of the range w 199 * other ranges, or the address of the range which owned 'the_range' 200 * if it becomes empty. 200 * if it becomes empty. 201 */ 201 */ 202 struct sos_kmem_range * 202 struct sos_kmem_range * 203 sos_kmem_cache_release_struct_range(struct sos 203 sos_kmem_cache_release_struct_range(struct sos_kmem_range *the_range); 204 204 205 205 206 #endif /* _SOS_KMEM_SLAB_H_ */ 206 #endif /* _SOS_KMEM_SLAB_H_ */
[ source navigation ] | [ diff markup ] | [ identifier search ] | [ general search ] |