/* 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);
 }