diff options
Diffstat (limited to 'sos-code-article6.5/sos/kmem_vmm.c')
| -rw-r--r-- | sos-code-article6.5/sos/kmem_vmm.c | 606 |
1 files changed, 606 insertions, 0 deletions
diff --git a/sos-code-article6.5/sos/kmem_vmm.c b/sos-code-article6.5/sos/kmem_vmm.c new file mode 100644 index 0000000..ea2fdf1 --- /dev/null +++ b/sos-code-article6.5/sos/kmem_vmm.c @@ -0,0 +1,606 @@ +/* Copyright (C) 2000 Thomas Petazzoni + Copyright (C) 2004 David Decotigny + + This program is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License + as published by the Free Software Foundation; either version 2 + of the License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, + USA. +*/ + +#include <sos/list.h> +#include <sos/physmem.h> +#include <hwcore/paging.h> +#include <sos/assert.h> + +#include "kmem_vmm.h" + +/** The structure of a range of kernel-space virtual addresses */ +struct sos_kmem_range +{ + sos_vaddr_t base_vaddr; + sos_count_t nb_pages; + + /* The slab owning this range, or NULL */ + struct sos_kslab *slab; + + struct sos_kmem_range *prev, *next; +}; +const int sizeof_struct_sos_kmem_range = sizeof(struct sos_kmem_range); + +/** The ranges are SORTED in (strictly) ascending base addresses */ +static struct sos_kmem_range *kmem_free_range_list, *kmem_used_range_list; + +/** The slab cache for the kmem ranges */ +static struct sos_kslab_cache *kmem_range_cache; + + + +/** Helper function to get the closest preceding or containing + range for the given virtual address */ +static struct sos_kmem_range * +get_closest_preceding_kmem_range(struct sos_kmem_range *the_list, + sos_vaddr_t vaddr) +{ + int nb_elements; + struct sos_kmem_range *a_range, *ret_range; + + /* kmem_range list is kept SORTED, so we exit as soon as vaddr >= a + range base address */ + ret_range = NULL; + list_foreach(the_list, a_range, nb_elements) + { + if (vaddr < a_range->base_vaddr) + return ret_range; + ret_range = a_range; + } + + /* This will always be the LAST range in the kmem area */ + return ret_range; +} + + +/** + * Helper function to lookup a free range large enough to hold nb_pages + * pages (first fit) + */ +static struct sos_kmem_range *find_suitable_free_range(sos_count_t nb_pages) +{ + int nb_elements; + struct sos_kmem_range *r; + + list_foreach(kmem_free_range_list, r, nb_elements) + { + if (r->nb_pages >= nb_pages) + return r; + } + + return NULL; +} + + +/** + * Helper function to add a_range in the_list, in strictly ascending order. + * + * @return The (possibly) new head of the_list + */ +static struct sos_kmem_range *insert_range(struct sos_kmem_range *the_list, + struct sos_kmem_range *a_range) +{ + struct sos_kmem_range *prec_used; + + /** Look for any preceding range */ + prec_used = get_closest_preceding_kmem_range(the_list, + a_range->base_vaddr); + /** insert a_range /after/ this prec_used */ + if (prec_used != NULL) + list_insert_after(the_list, prec_used, a_range); + else /* Insert at the beginning of the list */ + list_add_head(the_list, a_range); + + return the_list; +} + + +/** + * Helper function to retrieve the range owning the given vaddr, by + * scanning the physical memory first if vaddr is mapped in RAM + */ +static struct sos_kmem_range *lookup_range(sos_vaddr_t vaddr) +{ + struct sos_kmem_range *range; + + /* First: try to retrieve the physical page mapped at this address */ + sos_paddr_t ppage_paddr = SOS_PAGE_ALIGN_INF(sos_paging_get_paddr(vaddr)); + + if (ppage_paddr) + { + range = sos_physmem_get_kmem_range(ppage_paddr); + + /* If a page is mapped at this address, it is EXPECTED that it + is really associated with a range */ + SOS_ASSERT_FATAL(range != NULL); + } + + /* Otherwise scan the list of used ranges, looking for the range + owning the address */ + else + { + range = get_closest_preceding_kmem_range(kmem_used_range_list, + vaddr); + /* Not found */ + if (! range) + return NULL; + + /* vaddr not covered by this range */ + if ( (vaddr < range->base_vaddr) + || (vaddr >= (range->base_vaddr + range->nb_pages*SOS_PAGE_SIZE)) ) + return NULL; + } + + return range; +} + + +/** + * Helper function for sos_kmem_vmm_setup() to initialize a new range + * that maps a given area as free or as already used. + * This function either succeeds or halts the whole system. + */ +static struct sos_kmem_range * +create_range(sos_bool_t is_free, + sos_vaddr_t base_vaddr, + sos_vaddr_t top_vaddr, + struct sos_kslab *associated_slab) +{ + struct sos_kmem_range *range; + + SOS_ASSERT_FATAL(SOS_IS_PAGE_ALIGNED(base_vaddr)); + SOS_ASSERT_FATAL(SOS_IS_PAGE_ALIGNED(top_vaddr)); + + if ((top_vaddr - base_vaddr) < SOS_PAGE_SIZE) + return NULL; + + range = (struct sos_kmem_range*)sos_kmem_cache_alloc(kmem_range_cache, + SOS_KSLAB_ALLOC_ATOMIC); + SOS_ASSERT_FATAL(range != NULL); + + range->base_vaddr = base_vaddr; + range->nb_pages = (top_vaddr - base_vaddr) / SOS_PAGE_SIZE; + + if (is_free) + { + list_add_tail(kmem_free_range_list, + range); + } + else + { + sos_vaddr_t vaddr; + range->slab = associated_slab; + list_add_tail(kmem_used_range_list, + range); + + /* Ok, set the range owner for the pages in this page */ + for (vaddr = base_vaddr ; + vaddr < top_vaddr ; + vaddr += SOS_PAGE_SIZE) + { + sos_paddr_t ppage_paddr = sos_paging_get_paddr(vaddr); + SOS_ASSERT_FATAL((void*)ppage_paddr != NULL); + sos_physmem_set_kmem_range(ppage_paddr, range); + } + } + + return range; +} + + +sos_ret_t +sos_kmem_vmm_subsystem_setup(sos_vaddr_t kernel_core_base, + sos_vaddr_t kernel_core_top, + sos_vaddr_t bootstrap_stack_bottom_vaddr, + sos_vaddr_t bootstrap_stack_top_vaddr) +{ + struct sos_kslab *first_struct_slab_of_caches, + *first_struct_slab_of_ranges; + sos_vaddr_t first_slab_of_caches_base, + first_slab_of_caches_nb_pages, + first_slab_of_ranges_base, + first_slab_of_ranges_nb_pages; + struct sos_kmem_range *first_range_of_caches, + *first_range_of_ranges; + + list_init(kmem_free_range_list); + list_init(kmem_used_range_list); + + kmem_range_cache + = sos_kmem_cache_subsystem_setup_prepare(kernel_core_base, + kernel_core_top, + sizeof(struct sos_kmem_range), + & first_struct_slab_of_caches, + & first_slab_of_caches_base, + & first_slab_of_caches_nb_pages, + & first_struct_slab_of_ranges, + & first_slab_of_ranges_base, + & first_slab_of_ranges_nb_pages); + SOS_ASSERT_FATAL(kmem_range_cache != NULL); + + /* Mark virtual addresses 16kB - Video as FREE */ + create_range(TRUE, + SOS_KMEM_VMM_BASE, + SOS_PAGE_ALIGN_INF(BIOS_N_VIDEO_START), + NULL); + + /* Mark virtual addresses in Video hardware mapping as NOT FREE */ + create_range(FALSE, + SOS_PAGE_ALIGN_INF(BIOS_N_VIDEO_START), + SOS_PAGE_ALIGN_SUP(BIOS_N_VIDEO_END), + NULL); + + /* Mark virtual addresses Video - Kernel as FREE */ + create_range(TRUE, + SOS_PAGE_ALIGN_SUP(BIOS_N_VIDEO_END), + SOS_PAGE_ALIGN_INF(kernel_core_base), + NULL); + + /* Mark virtual addresses in Kernel code/data up to the bootstrap stack + as NOT FREE */ + create_range(FALSE, + SOS_PAGE_ALIGN_INF(kernel_core_base), + bootstrap_stack_bottom_vaddr, + NULL); + + /* Mark virtual addresses in the bootstrap stack as NOT FREE too, + but in another vmm region in order to be un-allocated later */ + create_range(FALSE, + bootstrap_stack_bottom_vaddr, + bootstrap_stack_top_vaddr, + NULL); + + /* Mark the remaining virtual addresses in Kernel code/data after + the bootstrap stack as NOT FREE */ + create_range(FALSE, + bootstrap_stack_top_vaddr, + SOS_PAGE_ALIGN_SUP(kernel_core_top), + NULL); + + /* Mark virtual addresses in the first slab of the cache of caches + as NOT FREE */ + SOS_ASSERT_FATAL(SOS_PAGE_ALIGN_SUP(kernel_core_top) + == first_slab_of_caches_base); + SOS_ASSERT_FATAL(first_struct_slab_of_caches != NULL); + first_range_of_caches + = create_range(FALSE, + first_slab_of_caches_base, + first_slab_of_caches_base + + first_slab_of_caches_nb_pages*SOS_PAGE_SIZE, + first_struct_slab_of_caches); + + /* Mark virtual addresses in the first slab of the cache of ranges + as NOT FREE */ + SOS_ASSERT_FATAL((first_slab_of_caches_base + + first_slab_of_caches_nb_pages*SOS_PAGE_SIZE) + == first_slab_of_ranges_base); + SOS_ASSERT_FATAL(first_struct_slab_of_ranges != NULL); + first_range_of_ranges + = create_range(FALSE, + first_slab_of_ranges_base, + first_slab_of_ranges_base + + first_slab_of_ranges_nb_pages*SOS_PAGE_SIZE, + first_struct_slab_of_ranges); + + /* Mark virtual addresses after these slabs as FREE */ + create_range(TRUE, + first_slab_of_ranges_base + + first_slab_of_ranges_nb_pages*SOS_PAGE_SIZE, + SOS_KMEM_VMM_TOP, + NULL); + + /* Update the cache subsystem so that the artificially-created + caches of caches and ranges really behave like *normal* caches (ie + those allocated by the normal slab API) */ + sos_kmem_cache_subsystem_setup_commit(first_struct_slab_of_caches, + first_range_of_caches, + first_struct_slab_of_ranges, + first_range_of_ranges); + + return SOS_OK; +} + + +/** + * Allocate a new kernel area spanning one or multiple pages. + * + * @eturn a new range structure + */ +struct sos_kmem_range *sos_kmem_vmm_new_range(sos_count_t nb_pages, + sos_ui32_t flags, + sos_vaddr_t * range_start) +{ + struct sos_kmem_range *free_range, *new_range; + + if (nb_pages <= 0) + return NULL; + + /* Find a suitable free range to hold the size-sized object */ + free_range = find_suitable_free_range(nb_pages); + if (free_range == NULL) + return NULL; + + /* If range has exactly the requested size, just move it to the + "used" list */ + if(free_range->nb_pages == nb_pages) + { + list_delete(kmem_free_range_list, free_range); + kmem_used_range_list = insert_range(kmem_used_range_list, + free_range); + /* The new_range is exactly the free_range */ + new_range = free_range; + } + + /* Otherwise the range is bigger than the requested size, split it. + This involves reducing its size, and allocate a new range, which + is going to be added to the "used" list */ + else + { + /* free_range split in { new_range | free_range } */ + new_range = (struct sos_kmem_range*) + sos_kmem_cache_alloc(kmem_range_cache, + (flags & SOS_KMEM_VMM_ATOMIC)? + SOS_KSLAB_ALLOC_ATOMIC:0); + if (! new_range) + return NULL; + + new_range->base_vaddr = free_range->base_vaddr; + new_range->nb_pages = nb_pages; + free_range->base_vaddr += nb_pages*SOS_PAGE_SIZE; + free_range->nb_pages -= nb_pages; + + /* free_range is still at the same place in the list */ + /* insert new_range in the used list */ + kmem_used_range_list = insert_range(kmem_used_range_list, + new_range); + } + + /* By default, the range is not associated with any slab */ + new_range->slab = NULL; + + /* If mapping of physical pages is needed, map them now */ + if (flags & SOS_KMEM_VMM_MAP) + { + int i; + for (i = 0 ; i < nb_pages ; i ++) + { + /* Get a new physical page */ + sos_paddr_t ppage_paddr + = sos_physmem_ref_physpage_new(! (flags & SOS_KMEM_VMM_ATOMIC)); + + /* Map the page in kernel space */ + if (ppage_paddr) + { + if (sos_paging_map(ppage_paddr, + new_range->base_vaddr + + i * SOS_PAGE_SIZE, + FALSE /* Not a user page */, + ((flags & SOS_KMEM_VMM_ATOMIC)? + SOS_VM_MAP_ATOMIC:0) + | SOS_VM_MAP_PROT_READ + | SOS_VM_MAP_PROT_WRITE)) + { + /* Failed => force unallocation, see below */ + sos_physmem_unref_physpage(ppage_paddr); + ppage_paddr = (sos_paddr_t)NULL; + } + else + { + /* Success : page can be unreferenced since it is + now mapped */ + sos_physmem_unref_physpage(ppage_paddr); + } + } + + /* Undo the allocation if failed to allocate or map a new page */ + if (! ppage_paddr) + { + sos_kmem_vmm_del_range(new_range); + return NULL; + } + + /* Ok, set the range owner for this page */ + sos_physmem_set_kmem_range(ppage_paddr, new_range); + } + } + /* ... Otherwise: Demand Paging will do the job */ + + if (range_start) + *range_start = new_range->base_vaddr; + + return new_range; +} + + +sos_ret_t sos_kmem_vmm_del_range(struct sos_kmem_range *range) +{ + int i; + struct sos_kmem_range *ranges_to_free; + list_init(ranges_to_free); + + SOS_ASSERT_FATAL(range != NULL); + SOS_ASSERT_FATAL(range->slab == NULL); + + /* Remove the range from the 'USED' list now */ + list_delete(kmem_used_range_list, range); + + /* + * The following do..while() loop is here to avoid an indirect + * recursion: if we call directly kmem_cache_free() from inside the + * current function, we take the risk to re-enter the current function + * (sos_kmem_vmm_del_range()) again, which may cause problem if it + * in turn calls kmem_slab again and sos_kmem_vmm_del_range again, + * and again and again. This may happen while freeing ranges of + * struct sos_kslab... + * + * To avoid this,we choose to call a special function of kmem_slab + * doing almost the same as sos_kmem_cache_free(), but which does + * NOT call us (ie sos_kmem_vmm_del_range()): instead WE add the + * range that is to be freed to a list, and the do..while() loop is + * here to process this list ! The recursion is replaced by + * classical iterations. + */ + do + { + /* Ok, we got the range. Now, insert this range in the free list */ + kmem_free_range_list = insert_range(kmem_free_range_list, range); + + /* Unmap the physical pages */ + for (i = 0 ; i < range->nb_pages ; i ++) + { + /* This will work even if no page is mapped at this address */ + sos_paging_unmap(range->base_vaddr + i*SOS_PAGE_SIZE); + } + + /* Eventually coalesce it with prev/next free ranges (there is + always a valid prev/next link since the list is circular). Note: + the tests below will lead to correct behaviour even if the list + is limited to the 'range' singleton, at least as long as the + range is not zero-sized */ + /* Merge with preceding one ? */ + if (range->prev->base_vaddr + range->prev->nb_pages*SOS_PAGE_SIZE + == range->base_vaddr) + { + struct sos_kmem_range *empty_range_of_ranges = NULL; + struct sos_kmem_range *prec_free = range->prev; + + /* Merge them */ + prec_free->nb_pages += range->nb_pages; + list_delete(kmem_free_range_list, range); + + /* Mark the range as free. This may cause the slab owning + the range to become empty */ + empty_range_of_ranges = + sos_kmem_cache_release_struct_range(range); + + /* If this causes the slab owning the range to become empty, + add the range corresponding to the slab at the end of the + list of the ranges to be freed: it will be actually freed + in one of the next iterations of the do{} loop. */ + if (empty_range_of_ranges != NULL) + { + list_delete(kmem_used_range_list, empty_range_of_ranges); + list_add_tail(ranges_to_free, empty_range_of_ranges); + } + + /* Set range to the beginning of this coelescion */ + range = prec_free; + } + + /* Merge with next one ? [NO 'else' since range may be the result of + the merge above] */ + if (range->base_vaddr + range->nb_pages*SOS_PAGE_SIZE + == range->next->base_vaddr) + { + struct sos_kmem_range *empty_range_of_ranges = NULL; + struct sos_kmem_range *next_range = range->next; + + /* Merge them */ + range->nb_pages += next_range->nb_pages; + list_delete(kmem_free_range_list, next_range); + + /* Mark the next_range as free. This may cause the slab + owning the next_range to become empty */ + empty_range_of_ranges = + sos_kmem_cache_release_struct_range(next_range); + + /* If this causes the slab owning the next_range to become + empty, add the range corresponding to the slab at the end + of the list of the ranges to be freed: it will be + actually freed in one of the next iterations of the + do{} loop. */ + if (empty_range_of_ranges != NULL) + { + list_delete(kmem_used_range_list, empty_range_of_ranges); + list_add_tail(ranges_to_free, empty_range_of_ranges); + } + } + + + /* If deleting the range(s) caused one or more range(s) to be + freed, get the next one to free */ + if (list_is_empty(ranges_to_free)) + range = NULL; /* No range left to free */ + else + range = list_pop_head(ranges_to_free); + + } + /* Stop when there is no range left to be freed for now */ + while (range != NULL); + + return SOS_OK; +} + + +sos_vaddr_t sos_kmem_vmm_alloc(sos_count_t nb_pages, + sos_ui32_t flags) +{ + struct sos_kmem_range *range + = sos_kmem_vmm_new_range(nb_pages, + flags, + NULL); + if (! range) + return (sos_vaddr_t)NULL; + + return range->base_vaddr; +} + + +sos_ret_t sos_kmem_vmm_free(sos_vaddr_t vaddr) +{ + struct sos_kmem_range *range = lookup_range(vaddr); + + /* We expect that the given address is the base address of the + range */ + if (!range || (range->base_vaddr != vaddr)) + return -SOS_EINVAL; + + /* We expect that this range is not held by any cache */ + if (range->slab != NULL) + return -SOS_EBUSY; + + return sos_kmem_vmm_del_range(range); +} + + +sos_ret_t sos_kmem_vmm_set_slab(struct sos_kmem_range *range, + struct sos_kslab *slab) +{ + if (! range) + return -SOS_EINVAL; + + range->slab = slab; + return SOS_OK; +} + +struct sos_kslab * sos_kmem_vmm_resolve_slab(sos_vaddr_t vaddr) +{ + struct sos_kmem_range *range = lookup_range(vaddr); + if (! range) + return NULL; + + return range->slab; +} + + +sos_bool_t sos_kmem_vmm_is_valid_vaddr(sos_vaddr_t vaddr) +{ + struct sos_kmem_range *range = lookup_range(vaddr); + return (range != NULL); +} |