[Kos-dev] kvalloc

[David Decotigny]

Bon, un premier jet...

L'idee, c'est qu'en fait, l'allocation de nouveau ranges dans kvalloc
peut se faire simplement et proprement sans appel a kvalloc => on
evite la recursivite. La technique est de faire en sorte que les
ranges nouveaux qu'on veut allouer sur de nouvelles pages soient
associes a un struct range* lui-meme stocke sur cette nouvelle page
(ca rappelle le mirroring, mais ca n'a rien a voir). C'est ca le point
fondamental de l'algo : on a des ranges dedies, donc des pages
physiques, remplis que de ranges.

L'algo suivant fait comme ci-dessus. J'ai fait en sorte que ca ne
fasse pas appel a une technique particuliere de stockage : liste,
arbre, ... ce qui compte, c'est qu'on soit sur qu'un range qui
contient au moins une page de 4k contenant au moins un struct range*
ne continendra en fait QUE des struct range* colles les uns aux autres
dans ce range. Et, que, quelle que soit la methode de stockage (arbre,
liste), on dispose d'un champ ou d'une methode "tail" qui donne le
struct range* d'adresse la plus elevee au sein des listes/arbres de
ranges.

Bref : la clef de tout le truc, c'est qu'on a certains ranges qui ne
contiennent que des struct range* (=> les "range_range"). C'est ces
ranges la qu'on manipule qd on doit allouer des ranges nouveaux.

4 fonctions externes :
  - find_range_in_free_ranges_list(nb_pages) : parcourt la liste/arbre des
    free a la recherche d'un range qui contient au moins
    nb_pages. renvoie NULL si introuvable . C'est une fonction
    "abstraite" : ca peut correspondre a un algo de type worst fit, best
    fit, first fit, ...
  - get_used_range_at_addr(addr) : parcourt la liste/l'arbre used a la
    recherche du range qui contient addr. NULL si introuvable.
  - move_no_merge range in (ranges_marques_used) : enleve range de la
    ou il etait avant + rajoute range dans la liste/l'arbre
    ranges_marques_used, sans faire de regroupement de ranges.
  - move_and_merge range in (ranges_marques_free) : idem mais avec des
    regroupements de ranges si possible. Accompagnes de la suppression
    de ranges liee aux regroupement.

1 macro/variable :
  - PREFERRED_RANGE_RANGE_SIZE : nombre de pages (4k) de range
    allouees quand on n'a plus de place dans les ranges de ranges pour
    stocker de nouveaux ranges.

1 remarque :
  - move_and_merge() est plus compliquee qu'il n'y parait : quand 2
    ranges doivent etre regroupes, elle doit verifier si une
    page physique de ranges ne doit pas etre liberee. Ou alors dans kgc.



struct range {
  addr_t start_address;
  unsigned nb_pages;

  // + champs pour la gestion de ranges_marques_free/used
  // typiquement : prev, next
};

static list_or_tree_t (ranges_marques_free);
static list_or_tree_t (ranges_marques_used);

addr_t kvalloc (nb_pages) {

  struct range *free_range = find_range_in_free_ranges_list(nb_pages);
  if (! free_range)
    return -1; /* No VM left !! */

  else if (nb_pages == free_range.nb_pages) then {
    move_no_merge free_range in (ranges_marques_used);
    /* Le page fault fait le reste ou on decide de mapper a la main */
    return free_range.start_address;
  }

  else if (nb_pages > free_range.nb_pages) then {

    /* Doit allouer un range */
    struct range *new_range;
    struct range *range_range = get_used_range_at_addr((ranges_marques_used).tail);

    if (! range_range)
      ASSERT_FATAL(!"Oops gravos !");

    /* BEGIN: Alloc of new_range */

    if (enough place in range_range for a new range to be allocated) then {
      new_range = (ranges_marques_used).tail + 1;   // + traiter cas tail=NULL
    } else {
      /* No place left in range_range for new_range => we need 1
         more range */
      struct range *free_range_range;
      struct range *new_range_range;

      free_range_range = find_range_in_free_ranges_list(PREFERRED_RANGE_RANGE_SIZE);
      if (! free_range_range)
        return -1; /* No VM left !!! */
      
      /* Ok : got it */
      
      new_range_range = (struct range*)free_range_range->start_address;

      if (free_range_range->nb_pages == PREFERRED_RANGE_RANGE_SIZE) then {
        // Nothing to do yet
      } else {
        /* Split this range */
        free_range_range->start_address += nb_pages*PAGE_SIZE;
        free_range_range->nb_pages      -= nb_pages;
      }

      // #PF or map_to_physical manual
      new_range_range->start_address = (addr_t) new_range_range; // self
      new_range_range->nb_pages = PREFERRED_RANGE_RANGE_SIZE;

      move_no_merge new_range_range in (ranges_marques_used);

      new_range = new_range_range + 1;
    }

    /* END: Alloc of new_range */

    new_range->nb_pages      = nb_pages;
    new_range->start_address = range->start_address;
    range->start_address    += nb_pages*PAGE_SIZE;
    range->nb_pages         -= nb_pages;

    move_no_merge new_range in (ranges_marques_used);

    return new_range->start_address;
  } /* if (nb_pages > range.nb_pages) */

  ASSERT_FATAL(!"!");
  return -1;
}



int kfree (addr) {

  for range in (ranges_marques_used) {

    if (range.start_addr == addr) then {
      unmap_whole_range_if_mapped(range);
      move_and_merge range in (ranges_marques_free);
      return 0;
    }

  }

  return -1;
}


A voir (a suivre)...


-- 
David Decotigny