kernel/fiasco/src/kern/mapping_tree.cpp

   1 INTERFACE:
   2
   3 #include "config.h"
   4 #include "l4_types.h"
   5 #include "lock.h"
   6 #include "mapping.h"
   7 #include "types.h"
   8
   9 #include <unique_ptr.h>
  10
  11 class Ram_quota;
  12
  13 class Simple_tree_submap_ops
  14 {
  15 };
  16
  17 /* The mapping database.
  18
  19  * This implementation encodes mapping trees in very compact arrays of
  20  * fixed sizes, prefixed by a tree header (Mapping_tree).  Array
  21  * sizes can vary from 4 mappings to 4<<15 mappings.  For each size,
  22  * we set up a slab allocator.  To grow or shrink the size of an
  23  * array, we have to allocate a larger or smaller tree from the
  24  * corresponding allocator and then copy the array elements.
  25  *
  26  * The array elements (Mapping) contain a tree depth element.  This
  27  * depth and the relative position in the array is all information we
  28  * need to derive tree structure information.  Here is an example:
  29  *
  30  * array
  31  * element   depth
  32  * number    value    comment
  33  * --------------------------
  34  * 0         0        Sigma0 mapping
  35  * 1         1        child of element #0 with depth 0
  36  * 2         2        child of element #1 with depth 1
  37  * 3         2        child of element #1 with depth 1
  38  * 4         3        child of element #3 with depth 2
  39  * 5         2        child of element #1 with depth 1
  40  * 6         3        child of element #5 with depth 2
  41  * 7         1        child of element #0 with depth 0
  42  *
  43  * This array is a pre-order encoding of the following tree:
  44  *
  45  *                   0
  46  *                /     \
  47  *               1       7
  48  *            /  |  \
  49  *           2   3   5
  50  *               |   |
  51  *               4   6
  52
  53  * The mapping database (Mapdb) is organized in a hierarchy of
  54  * frame-number-keyed maps of Mapping_trees (Treemap).  The top-level
  55  * Treemap contains mapping trees for superpages.  These mapping trees
  56  * may contain references to Treemaps for subpages.  (Original credits
  57  * for this idea: Christan Szmajda.)
  58  *
  59  *        Treemap
  60  *        -------------------------------
  61  *        | | | | | | | | | | | | | | | | array of ptr to 4M Mapping_tree's
  62  *        ---|---------------------------
  63  *           |
  64  *           v a Mapping_tree
  65  *           ---------------
  66  *           |             | tree header
  67  *           |-------------|
  68  *           |             | 4M Mapping *or* ptr to nested Treemap
  69  *           |             | e.g.
  70  *           |      ----------------| Treemap
  71  *           |             |        v array of ptr to 4K Mapping_tree's
  72  *           ---------------        -------------------------------
  73  *                                  | | | | | | | | | | | | | | | |
  74  *                                  ---|---------------------------
  75  *                                     |
  76  *                                     v a Mapping_tree
  77  *                                     ---------------
  78  *                                     |             | tree header
  79  *                                     |-------------|
  80  *                                     |             | 4K Mapping
  81  *                                     |             |
  82  *                                     |             |
  83  *                                     |             |
  84  *                                     ---------------
  85
  86  * IDEAS for enhancing this implementation:
  87
  88  * We often have to find a tree header corresponding to a mapping.
  89  * Currently, we do this by iterating backwards over the array
  90  * containing the mappings until we find the Sigma0 mapping, from
  91  * whose address we can compute the address of the tree header.  If
  92  * this becomes a problem, we could add one more byte to the mappings
  93  * with a hint (negative array offset) where to find the sigma0
  94  * mapping.  (If the hint value overflows, just iterate using the hint
  95  * value of the mapping we find with the first hint value.)  Another
  96  * idea (from Adam) would be to just look up the tree header by using
  97  * the physical address from the page-table lookup, but we would need
  98  * to change the interface of the mapping database for that (pass in
  99  * the physical address at all times), or we would have to include the
 100  * physical address (or just the address of the tree header) in the
 101  * Mapdb-user-visible Mapping (which could be different from the
 102  * internal tree representation).  (XXX: Implementing one of these
 103  * ideas is probably worthwile doing!)
 104
 105  * Instead of copying whole trees around when they grow or shrink a
 106  * lot, or copying parts of trees when inserting an element, we could
 107  * give up the array representation and add a "next" pointer to the
 108  * elements -- that is, keep the tree of mappings in a
 109  * pre-order-encoded singly-linked list (credits to: Christan Szmajda
 110  * and Adam Wiggins).  24 bits would probably be enough to encode that
 111  * pointer.  Disadvantages: Mapping entries would be larger, and the
 112  * cache-friendly space-locality of tree entries would be lost.
 113  */
 114
 115
 116 INTERFACE [!big_endian]:
 117 //
 118 // Mapping_tree
 119 // FIXME: do we need this depending on endianess ?
 120 struct Mapping_tree
 121 {
 122   typedef Mapping::Page Page;
 123   typedef Mapping::Pfn Pfn;
 124   typedef Mapping::Pcnt Pcnt;
 125
 126   enum Size_id
 127   {
 128     Size_id_min = 0,
 129     Size_id_max = 9             // can be up to 15 (4 bits)
 130   };
 131   // DATA
 132   unsigned _count: 16;          ///< Number of live entries in this tree.
 133   unsigned _size_id: 4;         ///< Tree size -- see number_of_entries().
 134   unsigned _empty_count: 11;    ///< Number of dead entries in this tree.
 135                                 //   XXX currently never read, except in
 136                                 //   sanity checks
 137
 138   unsigned _unused: 1;          // (make this 32 bits to avoid a compiler bug)
 139
 140   Mapping _mappings[0];
 141
 142 };
 143
 144
 145 INTERFACE [big_endian]:
 146 //
 147 // Mapping_tree
 148 // FIXME: do we need this depending on endianess ?
 149 struct Mapping_tree
 150 {
 151   typedef Mapping::Page Page;
 152   typedef Mapping::Pfn Pfn;
 153   typedef Mapping::Pcnt Pcnt;
 154
 155   enum Size_id
 156   {
 157     Size_id_min = 0,
 158     Size_id_max = 9             // can be up to 15 (4 bits)
 159   };
 160   // DATA
 161   unsigned _unused: 1;          // (make this 32 bits to avoid a compiler bug)
 162   unsigned _size_id: 4;         ///< Tree size -- see number_of_entries().
 163   unsigned _empty_count: 11;    ///< Number of dead entries in this tree.
 164                                 //   XXX currently never read, except in
 165                                 //   sanity checks
 166
 167   unsigned _count: 16;          ///< Number of live entries in this tree.
 168   Mapping _mappings[0];
 169 };
 170
 171 INTERFACE:
 172 //
 173 // class Physframe
 174 //
 175
 176 /** Array elements for holding frame-specific data. */
 177 class Base_mappable
 178 {
 179 public:
 180   typedef Mapping_tree::Page Page;
 181   // DATA
 182   cxx::unique_ptr<Mapping_tree> tree;
 183   typedef ::Lock Lock;
 184   Lock lock;
 185 }; // struct Physframe
 186
 187
 188 //---------------------------------------------------------------------------
 189 IMPLEMENTATION:
 190
 191 #include <cassert>
 192 #include <cstring>
 193
 194 #include "config.h"
 195 #include "globals.h"
 196 #include "kmem_slab.h"
 197 #include "ram_quota.h"
 198 #include "space.h"
 199 #include "std_macros.h"
 200
 201
 202 // Helpers
 203
 204 PUBLIC inline
 205 unsigned long
 206 Simple_tree_submap_ops::mem_size(Treemap const *) const
 207 { return 0; }
 208
 209 PUBLIC inline
 210 void
 211 Simple_tree_submap_ops::grant(Treemap *, Space *, Page_number) const
 212 {}
 213
 214 PUBLIC inline
 215 Space *
 216 Simple_tree_submap_ops::owner(Treemap const *) const
 217 { return 0; }
 218
 219 PUBLIC inline
 220 bool
 221 Simple_tree_submap_ops::is_partial(Treemap const *, Page_number, Page_number) const
 222 { return false; }
 223
 224 PUBLIC inline
 225 void
 226 Simple_tree_submap_ops::del(Treemap *) const
 227 {}
 228
 229 PUBLIC inline
 230 void
 231 Simple_tree_submap_ops::flush(Treemap *, Page_number, Page_number) const
 232 {}
 233
 234 //
 235 // Mapping-tree allocators
 236 //
 237
 238 enum Mapping_tree_size
 239 {
 240   Size_factor = 4,
 241   Size_id_max = 9               // can be up to 15 (4 bits)
 242 };
 243
 244 PUBLIC inline
 245 Mapping_tree::Size_id
 246 Mapping_tree::shrink()
 247 {
 248   unsigned sid = _size_id - 1;
 249   while (sid > 0 && ((static_cast<unsigned>(_count) << 2) < ((unsigned)Size_factor << sid)))
 250     --sid;
 251
 252   return Size_id(sid);
 253 }
 254
 255 PUBLIC inline
 256 Mapping_tree::Size_id
 257 Mapping_tree::bigger()
 258 { return Mapping_tree::Size_id(_size_id + 1); }
 259
 260 template<int SIZE_ID>
 261 struct Mapping_tree_allocator
 262 {
 263   Kmem_slab a;
 264   enum
 265   {
 266     Elem_size = (Size_factor << SIZE_ID) * sizeof (Mapping)
 267                 + sizeof(Mapping_tree)
 268   };
 269
 270   Mapping_tree_allocator(Kmem_slab **array)
 271   : a(Elem_size, Mapping::Alignment, "Mapping_tree")
 272   { array[SIZE_ID] = &a; }
 273 };
 274
 275 template<int SIZE_ID_MAX>
 276 struct Mapping_tree_allocators;
 277
 278 template<>
 279 struct Mapping_tree_allocators<0>
 280 {
 281   Mapping_tree_allocator<0> a;
 282   Mapping_tree_allocators(Kmem_slab **array) : a(array) {}
 283 };
 284
 285 template<int SIZE_ID_MAX>
 286 struct Mapping_tree_allocators
 287 {
 288
 289   Mapping_tree_allocator<SIZE_ID_MAX> a;
 290   Mapping_tree_allocators<SIZE_ID_MAX - 1> n;
 291
 292   Mapping_tree_allocators(Kmem_slab **array) : a(array), n(array) {}
 293 };
 294
 295 static Kmem_slab *_allocators[Size_id_max + 1];
 296 static Mapping_tree_allocators<Size_id_max> _mapping_tree_allocators(_allocators);
 297
 298 static
 299 Kmem_slab *
 300 allocator_for_treesize(int size)
 301 {
 302   return _allocators[size];
 303 }
 304
 305 //
 306 // class Mapping_tree
 307 //
 308
 309 PUBLIC static
 310 inline NEEDS["space.h"]
 311 Ram_quota *
 312 Mapping_tree::quota(Space *space)
 313 {
 314   return space->ram_quota();
 315 }
 316
 317 PUBLIC
 318 void*
 319 Mapping_tree::operator new (size_t, Mapping_tree::Size_id size_id) throw()
 320 { return allocator_for_treesize(size_id)->alloc(); }
 321
 322 PUBLIC
 323 void
 324 Mapping_tree::operator delete (void* block)
 325 {
 326   if (!block)
 327     return;
 328
 329   // Try to guess right allocator object -- XXX unportable!
 330   Mapping_tree* t = static_cast<Mapping_tree*>(block);
 331
 332   t->check_integrity();
 333
 334   allocator_for_treesize(t->_size_id)->free(block);
 335 }
 336
 337 PUBLIC //inline NEEDS[Mapping_depth, Mapping_tree::last]
 338 Mapping_tree::Mapping_tree(Size_id size_id, Page page,
 339                            Space *owner)
 340 {
 341   _count = 1;                   // 1 valid mapping
 342   _size_id = size_id;           // size is equal to Size_factor << 0
 343 #ifndef NDEBUG
 344   _empty_count = 0;             // no gaps in tree representation
 345 #endif
 346
 347   _mappings[0].set_depth(Mapping::Depth_root);
 348   _mappings[0].set_page(page);
 349   _mappings[0].set_space(owner);
 350
 351   _mappings[1].set_depth(Mapping::Depth_end);
 352
 353   // We also always set the end tag on last entry so that we can
 354   // check whether it has been overwritten.
 355   last()->set_depth(Mapping::Depth_end);
 356 }
 357
 358 PUBLIC
 359 Mapping_tree::~Mapping_tree()
 360 {
 361   // special case for copied mapping trees
 362   for (Mapping *m = _mappings; m < end() && !m->is_end_tag(); ++m)
 363     {
 364       if (!m->submap() && !m->unused())
 365         quota(m->space())->free(sizeof(Mapping));
 366     }
 367 }
 368
 369 PUBLIC //inline NEEDS[Mapping_depth, Mapping_tree::last]
 370 Mapping_tree::Mapping_tree(Size_id size_id, Mapping_tree* from_tree)
 371 {
 372   _size_id = size_id;
 373   last()->set_depth(Mapping::Depth_end);
 374
 375   copy_compact_tree(this, from_tree);
 376 }
 377
 378 // public routines with inline implementations
 379 PUBLIC inline NEEDS[Mapping_tree_size]
 380 unsigned
 381 Mapping_tree::number_of_entries() const
 382 {
 383   return Size_factor << (unsigned long)_size_id;
 384 }
 385
 386 PUBLIC inline
 387 Mapping *
 388 Mapping_tree::mappings()
 389 {
 390   return & _mappings[0];
 391 }
 392
 393 PUBLIC inline
 394 bool
 395 Mapping_tree::is_empty() const
 396 {
 397   return _count == 0;
 398 }
 399
 400 PUBLIC inline NEEDS[Mapping_tree::mappings, Mapping_tree::number_of_entries]
 401 Mapping *
 402 Mapping_tree::end()
 403 {
 404   return mappings() + number_of_entries();
 405 }
 406
 407 PUBLIC inline NEEDS[Mapping_tree::end]
 408 Mapping *
 409 Mapping_tree::last()
 410 {
 411   return end() - 1;
 412 }
 413
 414 // A utility function to find the tree header belonging to a mapping.
 415
 416 /** Our Mapping_tree.
 417     @return the Mapping_tree we are in.
 418  */
 419 PUBLIC static
 420 Mapping_tree *
 421 Mapping_tree::head_of(Mapping *m)
 422 {
 423   while (m->depth() > Mapping::Depth_root)
 424     {
 425       // jump in bigger steps if this is not a free mapping
 426       if (m->depth() <= Mapping::Depth_max)
 427         {
 428           m -= m->depth();
 429           continue;
 430         }
 431
 432       m--;
 433     }
 434
 435   return reinterpret_cast<Mapping_tree *>
 436     (reinterpret_cast<char *>(m) - sizeof(Mapping_tree));
 437   // We'd rather like to use offsetof as follows, but it's unsupported
 438   // for non-POD classes.  So we instead rely on GCC's zero-length
 439   // array magic (sizeof(Mapping_tree) is the size of the header
 440   // without the array).
 441   // return reinterpret_cast<Mapping_tree *>
 442   //   (reinterpret_cast<char *>(m) - offsetof(Mapping_tree, _mappings));
 443 }
 444
 445 /** Next mapping in the mapping tree.
 446     @param t head of mapping tree, if available
 447     @return the next mapping in the mapping tree.  If the mapping has
 448     children, it is the first child.  Otherwise, if the mapping has a
 449     sibling, it's the next sibling.  Otherwise, if the mapping is the
 450     last sibling or only child, it's the mapping's parent.
 451  */
 452 PUBLIC inline
 453 Mapping *
 454 Mapping_tree::next(Mapping *m)
 455 {
 456   for (m++; m < end() && ! m->is_end_tag(); m++)
 457     if (! m->unused())
 458       return m;
 459
 460   return 0;
 461 }
 462
 463 /** Next child mapping of a given parent mapping.  This
 464     function traverses the mapping tree like next(); however, it
 465     stops (and returns 0) if the next mapping is outside the subtree
 466     starting with parent.
 467     @param parent Parent mapping
 468     @return the next child mapping of a given parent mapping
 469  */
 470 PUBLIC inline NEEDS[Mapping_tree::next]
 471 Mapping *
 472 Mapping_tree::next_child(Mapping *parent, Mapping *current_child)
 473 {
 474   // Find the next valid entry in the tree structure.
 475   Mapping *m = next(current_child);
 476
 477   // If we didn't find an entry, or if the entry cannot be a child of
 478   // "parent", return 0
 479   if (m == 0 || m->depth() <= parent->depth())
 480     return 0;
 481
 482   return m;                     // Found!
 483 }
 484
 485 // This function copies the elements of mapping tree src to mapping
 486 // tree dst, ignoring empty elements (that is, compressing the
 487 // source tree.  In-place compression is supported.
 488 PUBLIC static
 489 void
 490 Mapping_tree::copy_compact_tree(Mapping_tree *dst, Mapping_tree *src)
 491 {
 492   unsigned src_count = src->_count; // Store in local variable before
 493                                     // it can get overwritten
 494
 495   // Special case: cannot in-place compact a full tree
 496   if (src == dst && src->number_of_entries() == src_count)
 497     return;
 498
 499   // Now we can assume the resulting tree will not be full.
 500   assert (src_count < dst->number_of_entries());
 501
 502   dst->_count = 0;
 503 #ifndef NDEBUG
 504   dst->_empty_count = 0;
 505 #endif
 506
 507   Mapping *d = dst->mappings();
 508
 509   for (Mapping *s = src->mappings();
 510        s && !s->is_end_tag();
 511        s = src->next(s))
 512     {
 513       *d++ = *s;
 514       dst->_count += 1;
 515     }
 516
 517   assert (dst->_count == src_count); // Same number of entries
 518   assert (d < dst->end());
 519   // Room for one more entry (the Mapping::Depth_end entry)
 520
 521   d->set_depth(Mapping::Depth_end);
 522   dst->last()->set_depth(Mapping::Depth_end);
 523 } // copy_compact_tree()
 524
 525 // Don't inline this function -- it eats a lot of stack space!
 526 PUBLIC // inline NEEDS[Mapping::data, Mapping::unused, Mapping::is_end_tag,
 527        //              Mapping_tree::end, Mapping_tree::number_of_entries]
 528 void
 529 Mapping_tree::check_integrity(Space *owner = (Space*)-1)
 530 {
 531   (void)owner;
 532 #ifndef NDEBUG
 533   bool enter_ke = false;
 534   // Sanity checking
 535   if (// Either each entry is used
 536       !(number_of_entries() == static_cast<unsigned>(_count) + _empty_count
 537       // Or the last used entry is end tag
 538         || mappings()[_count + _empty_count].is_end_tag()))
 539     {
 540       printf("mapdb consistency error: "
 541              "%d == %d + %d || mappings()[%d + %d].is_end_tag()=%d\n",
 542              number_of_entries(), static_cast<unsigned>(_count), _empty_count,
 543              _count, _empty_count, mappings()[_count + _empty_count].is_end_tag());
 544       enter_ke = true;
 545     }
 546
 547   Mapping *m = mappings();
 548
 549   if (!(m->is_end_tag()   // When the tree was copied to a new one
 550         || (!m->unused()  // The first entry is never unused.
 551             && m->depth() == 0
 552             && (owner == (Space *)-1 || m->space() == owner))))
 553     {
 554       printf("mapdb corrupted: owner=%p\n"
 555              "  m=%p (end: %s depth: %d space: %p page: %lx)\n",
 556              owner, m, m->is_end_tag() ? "yes" : "no", m->depth(), m->space(),
 557              cxx::int_value<Page>(m->page()));
 558       enter_ke = true;
 559     }
 560
 561   unsigned used = 0, dead = 0;
 562
 563   while (m < end() && !m->is_end_tag())
 564     {
 565       if (m->unused())
 566         dead++;
 567       else
 568         used++;
 569
 570       m++;
 571     }
 572
 573   if (enter_ke |= _count != used)
 574     printf("mapdb: _count=%d != used=%d\n", _count, used);
 575   if (enter_ke |= _empty_count != dead)
 576     printf("mapdb: _empty_count=%d != dead=%d\n", _empty_count, dead);
 577
 578   if (enter_ke)
 579     {
 580       printf("mapdb:    from %p on CPU%d\n",
 581              __builtin_return_address(0),
 582              cxx::int_value<Cpu_number>(current_cpu()));
 583       kdb_ke("mapdb");
 584     }
 585
 586 #endif // ! NDEBUG
 587 }
 588
 589
 590 /**
 591  * Use this function to reset a the tree to empty.
 592  *
 593  * In the case where a tree was copied to a new one you have to use
 594  * this function to prevent the node iteration in the destructor.
 595  */
 596 PUBLIC inline
 597 void
 598 Mapping_tree::reset()
 599 {
 600   _count = 0;
 601   _empty_count = 0;
 602   _mappings[0].set_depth(Mapping::Depth_end);
 603 }
 604
 605 PUBLIC inline NEEDS[Mapping_tree::next, <cassert>]
 606 Treemap *
 607 Mapping_tree::find_submap(Mapping* parent)
 608 {
 609   assert (! parent->submap());
 610
 611   // We need just one step to find a possible submap, because they are
 612   // always a parent's first child.
 613   Mapping* m = next(parent);
 614
 615   if (m && m->submap())
 616     return m->submap();
 617
 618   return 0;
 619 }
 620
 621 PUBLIC inline NEEDS["ram_quota.h"]
 622 Mapping *
 623 Mapping_tree::allocate(Ram_quota *payer, Mapping *parent,
 624                        bool insert_submap = false)
 625 {
 626   Auto_quota<Ram_quota> q(payer, sizeof(Mapping));
 627   if (EXPECT_FALSE(!q))
 628     return 0;
 629
 630   // After locating the right place for the new entry, it will be
 631   // stored there (if this place is empty) or the following entries
 632   // moved by one entry.
 633
 634   // We cannot continue if the last array entry is not free.  This
 635   // only happens if an earlier call to free() with this mapping tree
 636   // couldn't allocate a bigger array.  In this case, signal an
 637   // out-of-memory condition.
 638   if (EXPECT_FALSE (! last()->unused()))
 639     return 0;
 640
 641   // If the parent mapping already has the maximum depth, we cannot
 642   // insert a child.
 643   if (EXPECT_FALSE (parent->depth() == Mapping::Depth_max))
 644     return 0;
 645
 646   //allocation is done, so...
 647   q.release();
 648
 649   Mapping *insert = parent + 1, *free = 0;
 650   // - Find an insertion point for the new entry. Acceptable insertion
 651   //   points are either before a sibling (same depth) or at the end
 652   //   of the subtree; for submap insertions, it's always before
 653   //   the first sibling.  "insert" keeps track of the last
 654   //   acceptable insertion point.
 655   // - Find a free entry in the array encoding the subtree ("free").
 656   //   There might be none; in this case, we stop at the end of the
 657   //   subtree.
 658
 659   if (!insert_submap)
 660     for (; insert < end(); ++insert)
 661       {
 662         // End of subtree?  If we reach this point, this is our insert spot.
 663         if (insert->is_end_tag() || insert->depth() <= parent->depth())
 664           break;
 665
 666         if (insert->unused())
 667           free = insert;
 668         else if (free           // Only look for insert spots after free
 669                  && insert->depth() <= parent->depth() + 1)
 670           break;
 671       }
 672
 673   assert (insert);
 674   assert (free == 0 || (free->unused() && free < insert));
 675
 676   // We now update "free" to point to a free spot that is acceptable
 677   // as well.
 678
 679   if (free)
 680     {
 681       // "free" will be the latest free spot before the "insert" spot.
 682       // If there is anything between "free" and "insert", move it
 683       // upward to make space just before insert.
 684       while (free + 1 != insert)
 685         {
 686           *free = *(free + 1);
 687           free++;
 688         }
 689
 690 #ifndef NDEBUG
 691       // Tree-header maintenance
 692       _empty_count -= 1;        // Allocated dead entry
 693 #endif
 694     }
 695   else                          // free == 0
 696     {
 697       // There was no free spot in the subtree.  Move everything
 698       // downward until we have free space.  This is guaranteed to
 699       // succeed, because we ensured earlier that the last entry of
 700       // the array is free.
 701
 702       free = insert;            // This will be the free spot
 703
 704       // Find empty spot
 705       while (! insert->unused())
 706         insert++;
 707
 708       // Tree maintenance: handle end tag, empty count
 709       if (insert->is_end_tag())
 710         {
 711           // Need to move end tag.
 712           if (insert + 1 < end())
 713             insert++;           // Arrange for copying end tag as well
 714         }
 715 #ifndef NDEBUG
 716       else
 717         _empty_count -= 1;      // Allocated dead entry
 718 #endif
 719
 720       // Move mappings
 721       while (insert > free)
 722         {
 723           *insert = *(insert - 1);
 724           --insert;
 725         }
 726     }
 727
 728   _count += 1;          // Adding an alive entry
 729
 730   // found a place to insert new child (free).
 731   free->set_depth(insert_submap ? (unsigned)Mapping::Depth_submap
 732                                 : parent->depth() + 1);
 733
 734   return free;
 735 }
 736
 737 PUBLIC inline NEEDS["ram_quota.h"]
 738 void
 739 Mapping_tree::free_mapping(Ram_quota *q, Mapping *m)
 740 {
 741   assert (!m->unused() && !m->is_end_tag());
 742   q->free(sizeof(Mapping));
 743   m->set_unused();
 744   --_count;
 745 }
 746
 747 PUBLIC template< typename SUBMAP_OPS >
 748 void
 749 Mapping_tree::flush(Mapping *parent, bool me_too,
 750                     Pcnt offs_begin, Pcnt offs_end,
 751                     SUBMAP_OPS const &submap_ops = SUBMAP_OPS())
 752 {
 753   assert (! parent->unused());
 754
 755   // This is easy to do: We just have to iterate over the array
 756   // encoding the tree.
 757   Mapping *start_of_deletions = parent;
 758   unsigned p_depth = parent->depth();
 759   unsigned deleted = 0;
 760 #ifndef NDEBUG
 761   unsigned empty_elems_passed = 0;
 762 #endif
 763
 764   if (me_too)
 765     {
 766       free_mapping(quota(parent->space()), parent);
 767       deleted++;
 768     }
 769   else
 770     start_of_deletions++;
 771
 772   unsigned m_depth = p_depth;
 773
 774   for (Mapping* m = parent + 1;
 775        m < end() && ! m->is_end_tag();
 776        m++)
 777     {
 778       if (unsigned (m->depth()) <= p_depth)
 779         {
 780           // Found another data element -- stop deleting.  Since we
 781           // created holes in the tree representation, account for it.
 782 #ifndef NDEBUG
 783           _empty_count += deleted;
 784 #endif
 785           return;
 786         }
 787
 788       if (m->unused())
 789         {
 790 #ifndef NDEBUG
 791           empty_elems_passed++;
 792 #endif
 793           continue;
 794         }
 795
 796       Space *space;
 797       if (Treemap* submap = m->submap())
 798         {
 799           space = submap_ops.owner(submap);
 800           if (! me_too
 801               // Check for immediate child.  Note: It's a bad idea to
 802               // call m->parent() because that would iterate backwards
 803               // over already-deleted entries.
 804               && m_depth == p_depth
 805               && submap_ops.is_partial(submap, offs_begin, offs_end))
 806             {
 807               submap_ops.flush(submap, offs_begin, offs_end);
 808
 809               start_of_deletions++;
 810               continue;
 811             }
 812           else
 813             submap_ops.del(submap);
 814         }
 815       else    // Found a real mapping
 816         {
 817           space = m->space();
 818           m_depth = m->depth();
 819         }
 820
 821       // Delete the element.
 822       free_mapping(quota(space), m);
 823       deleted++;
 824     }
 825
 826   // We deleted stuff at the end of the array -- move end tag
 827   if (start_of_deletions < end())
 828     {
 829       start_of_deletions->set_depth(Mapping::Depth_end);
 830
 831 #ifndef NDEBUG
 832       // also, reduce number of free entries
 833       _empty_count -= empty_elems_passed;
 834 #endif
 835     }
 836 }
 837
 838 PUBLIC template< typename SUBMAP_OPS >
 839 bool
 840 Mapping_tree::grant(Mapping* m, Space *new_space, Page page,
 841                     SUBMAP_OPS const &submap_ops = SUBMAP_OPS())
 842 {
 843   unsigned long _quota = sizeof(Mapping);
 844   Treemap* submap = find_submap(m);
 845   if (submap)
 846     _quota += submap_ops.mem_size(submap);
 847
 848   if (!quota(new_space)->alloc(_quota))
 849     return false;
 850
 851   Space *old_space = m->space();
 852
 853   m->set_space(new_space);
 854   m->set_page(page);
 855
 856   if (submap)
 857     submap_ops.grant(submap, new_space, page);
 858
 859   quota(old_space)->free(_quota);
 860   return true;
 861 }
 862
 863 PUBLIC inline
 864 Mapping *
 865 Mapping_tree::lookup(Space *space, Page page)
 866 {
 867
 868   Mapping *m;
 869
 870   for (m = mappings(); m; m = next(m))
 871     {
 872       assert (!m->submap());
 873       if (m->space() == space && m->page() == page)
 874         return m;
 875     }
 876
 877   return 0;
 878 }
 879
 880
 881 PUBLIC
 882 Mapping *
 883 Base_mappable::lookup(Space *space, Page page)
 884 {
 885   // get and lock the tree.
 886   if (EXPECT_FALSE(lock.lock() == Lock::Invalid))
 887     return 0;
 888   Mapping_tree *t = tree.get();
 889   assert (t);
 890   if (Mapping *m = t->lookup(space, page))
 891     return m;
 892
 893   lock.clear();
 894   return 0;
 895 }
 896
 897 PUBLIC inline
 898 Mapping *
 899 Base_mappable::insert(Mapping* parent, Space *space, Page page)
 900 {
 901   Mapping_tree* t = tree.get();
 902   if (!t)
 903     {
 904       assert (parent == 0);
 905       Auto_quota<Ram_quota> q(Mapping_tree::quota(space), sizeof(Mapping));
 906       if (EXPECT_FALSE(!q))
 907         return 0;
 908
 909       Mapping_tree::Size_id min_size = Mapping_tree::Size_id_min;
 910       cxx::unique_ptr<Mapping_tree> new_tree(new (min_size) Mapping_tree (min_size, page, space));
 911
 912       if (EXPECT_FALSE(!new_tree))
 913         return 0;
 914
 915       tree = cxx::move(new_tree);
 916       q.release();
 917       return tree->mappings();
 918     }
 919
 920   Mapping *free = t->allocate(Mapping_tree::quota(space), parent, false);
 921
 922   if (EXPECT_FALSE(!free))
 923         return 0;
 924
 925   free->set_space(space);
 926   free->set_page(page);
 927
 928   t->check_integrity();
 929   return free;
 930 }
 931
 932
 933 PUBLIC
 934 void
 935 Base_mappable::pack()
 936 {
 937   // Before we unlock the tree, we need to make sure that there is
 938   // room for at least one new mapping.  In particular, this means
 939   // that the last entry of the array encoding the tree must be free.
 940
 941   // (1) When we use up less than a quarter of all entries of the
 942   // array encoding the tree, copy to a smaller tree.  Otherwise, (2)
 943   // if the last entry is free, do nothing.  Otherwise, (3) if less
 944   // than 3/4 of the entries are used, compress the tree.  Otherwise,
 945   // (4) copy to a larger tree.
 946
 947   Mapping_tree *t = tree.get();
 948   bool maybe_out_of_memory = false;
 949
 950   do // (this is not actually a loop, just a block we can "break" out of)
 951     {
 952       // (1) Do we need to allocate a smaller tree?
 953       if (t->_size_id > Mapping_tree::Size_id_min // must not be smallest size
 954           && (static_cast<unsigned>(t->_count) << 2) < t->number_of_entries())
 955         {
 956           Mapping_tree::Size_id sid = t->Mapping_tree::shrink();
 957           cxx::unique_ptr<Mapping_tree> new_t(new (sid) Mapping_tree(sid, t));
 958
 959           if (new_t)
 960             {
 961               // ivalidate node 0 because we must not free the quota for it
 962               t->reset();
 963               t = new_t.get();
 964
 965               // Register new tree.
 966               tree = cxx::move(new_t);
 967
 968               break;
 969             }
 970         }
 971
 972       // (2) Is last entry is free?
 973       if (t->last()->unused())
 974         break;                  // OK, last entry is free.
 975
 976       // Last entry is not free -- either compress current array
 977       // (i.e., move free entries to end of array), or allocate bigger
 978       // array.
 979
 980       // (3) Should we compress the tree?
 981       // We also try to compress if we cannot allocate a bigger
 982       // tree because there is no bigger tree size.
 983       if (t->_count < (t->number_of_entries() >> 2)
 984                       + (t->number_of_entries() >> 1)
 985           || t->_size_id == Size_id_max) // cannot enlarge?
 986         {
 987           if (t->_size_id == Size_id_max)
 988             maybe_out_of_memory = true;
 989
 990           Mapping_tree::copy_compact_tree(t, t); // in-place compression
 991
 992           break;
 993         }
 994
 995       // (4) OK, allocate a bigger array.
 996
 997       Mapping_tree::Size_id sid = t->bigger();
 998       cxx::unique_ptr<Mapping_tree> new_t(new (sid) Mapping_tree(sid, t));
 999
1000       if (new_t)
1001         {
1002           // ivalidate node 0 because we must not free the quota for it
1003           t->reset();
1004           t = new_t.get();
1005
1006           // Register new tree.
1007           tree = cxx::move(new_t);
1008         }
1009       else
1010         {
1011           // out of memory -- just do tree compression and hope that helps.
1012           maybe_out_of_memory = true;
1013
1014           Mapping_tree::copy_compact_tree(t, t); // in-place compression
1015         }
1016     }
1017   while (false);
1018
1019   // The last entry of the tree should now be free -- exept if we're
1020   // out of memory.
1021   assert (t->last()->unused() || maybe_out_of_memory);
1022   (void) maybe_out_of_memory;
1023 }
1024
1025
1026