1 /* 2 * Copyright (c) 1998, 2002 Michael J. Roberts. All Rights Reserved. 3 * 4 * Please see the accompanying license file, LICENSE.TXT, for information 5 * on using and copying this software. 6 */ 7 /* 8 Name 9 vmpool.h - VM constant pool manager 10 Function 11 12 Notes 13 14 Modified 15 10/20/98 MJRoberts - Creation 16 */ 17 18 #ifndef VMPOOL_H 19 #define VMPOOL_H 20 21 #include <stdlib.h> 22 #include <memory.h> 23 24 #include "vmtype.h" 25 26 /* include the pool selection mechanism */ 27 #include "vmpoolsl.h" 28 29 /* ------------------------------------------------------------------------ */ 30 /* 31 * Constant pool page information. This structure tracks memory for one 32 * page. 33 */ 34 struct CVmPool_pg 35 { 36 /* memory containing the data in this page */ 37 const char *mem; 38 }; 39 40 41 /* ------------------------------------------------------------------------ */ 42 /* 43 * Constant Pool Backing Store Interface. This is an abstract interface 44 * that pool clients must implement to provide the pool with the means 45 * of loading pages. 46 * 47 * Note that the backing store, like the pool itself, is considered 48 * read-only by the pool manager. The pool manager never needs to write 49 * data to the backing store, and expects the backing store to remain 50 * constant throughout the existence of the pool (hence the pool never 51 * needs to reload any data from the backing store that it already has 52 * in cache). 53 */ 54 class CVmPoolBackingStore 55 { 56 public: 57 /* 58 * since this class is abstract, make sure all subclasses have virtual 59 * destructors 60 */ ~CVmPoolBackingStore()61 virtual ~CVmPoolBackingStore() { } 62 63 /* 64 * Determine the total number of pages that are available to be 65 * loaded. Implementations of the pool manager that pre-load all 66 * pages use this function to determine how many pages are available 67 * for loading. 68 */ 69 virtual size_t vmpbs_get_page_count() = 0; 70 71 /* 72 * Get the common page size in the underying store. Individual 73 * pages may not use the entire page size, but no page may be larger 74 * than the common size. 75 */ 76 virtual size_t vmpbs_get_common_page_size() = 0; 77 78 /* 79 * Given a starting offset and a page size, calculate how much space is 80 * actually needed for the page at the offset. This is provided to 81 * allow for partial pages, which don't need the full page size 82 * allocated. Simple implementations can simply always return the full 83 * page size. 84 */ 85 virtual size_t vmpbs_get_page_size(pool_ofs_t ofs, size_t page_size) = 0; 86 87 /* 88 * Given a starting offset, allocate space for the given page and 89 * load it into memory. page_size is the normal page size in bytes, 90 * and load_size is the actual number of bytes to be allocated and 91 * loaded (this will be the value previously returned by 92 * vmpbs_get_page_size for the page). 93 * 94 * This should throw an exception if an error occurs. 95 */ 96 virtual const char 97 *vmpbs_alloc_and_load_page(pool_ofs_t ofs, size_t page_size, 98 size_t load_size) = 0; 99 100 /* 101 * Delete memory allocated by vmpbs_alloc_and_load_page(). The pool 102 * will call this for each page previously allocated. 'page_size' 103 * is the normal page size in bytes for the entire pool. 104 */ 105 virtual void vmpbs_free_page(const char *mem, pool_ofs_t ofs, 106 size_t page_size) = 0; 107 108 /* 109 * Given a starting offset, load the page into the given memory, 110 * which is allocated and managed by the caller. page_size is the 111 * normal page size in bytes, and load_size is the actual number of 112 * bytes to be loaded (this will be the value previously returned by 113 * vmpbs_get_page_size for the page). 114 * 115 * This should throw an exception if an error occurs. 116 */ 117 virtual void vmpbs_load_page(pool_ofs_t ofs, size_t page_size, 118 size_t load_size, char *mem) = 0; 119 120 /* 121 * Determine if my pages are writable. Returns true if so, false if 122 * not. If the pool pages are directly mapped to the underlying 123 * data file, this should return false. For example, an 124 * implementation for a palm-top computer without an external 125 * storage device might simply store the image file directly in 126 * memory, and the backing store would map directly onto this memory 127 * so that the original copy of the image file in memory can be used 128 * as the loaded version as well. In such cases, the backing store 129 * should certainly not be writable. For an implementation that 130 * copies data from an external storage device (typically a hard 131 * disk), writing to the backing store copy would cause no change to 132 * the original image file data, hence this can return true in such 133 * cases. 134 */ vmpbs_is_writable()135 virtual int vmpbs_is_writable() { return FALSE; } 136 }; 137 138 139 /* ------------------------------------------------------------------------ */ 140 /* 141 * Base constant memory pool class 142 */ 143 class CVmPool 144 { 145 public: CVmPool()146 CVmPool() { } ~CVmPool()147 virtual ~CVmPool() { } 148 149 /* 150 * Get the dynamic data manager for the pool. If the pool supports 151 * dynamic data, it should return a non-null pointer. If the pool 152 * doesn't support dynamic data, it should return null. 153 */ get_dynamic_ifc()154 virtual class CVmPoolDynamic *get_dynamic_ifc() { return 0; } 155 156 /* 157 * Attach to the given backing store to provide the the page data. 158 */ 159 virtual void 160 attach_backing_store(class CVmPoolBackingStore *backing_store) = 0; 161 162 /* 163 * Detach from backing store - this must be called before the backing 164 * store object can be deleted. 165 */ detach_backing_store()166 virtual void detach_backing_store() { backing_store_ = 0; } 167 168 /* 169 * Translate an address from a pool offset to a physical location. 170 * Note that translating an address may invalidate a previously 171 * translated address in a swapping implementation of the pool manager, 172 * so callers should take care to assume only one translated address in 173 * a given pool is valid at a time. 174 * 175 * Because this routine is called extremely frequently, we don't make 176 * it a virtual. Instead, we depend upon the final subclass to define 177 * the method as a non-virtual, so that it can be in-lined. This means 178 * that pool object references must all be declared with the final 179 * subclass. 180 */ 181 /* virtual const char *get_ptr(pool_ofs_t ofs) = 0; */ 182 183 /* 184 * Translate an address from a pool offset to a physical location, and 185 * return a writable pointer to the location. This will fail for any 186 * type of pool implementation that doesn't support writable memory 187 * pointers (for example, the swapping pool doesn't allow write 188 * pointers, because it doesn't keep track of dirty pages when 189 * performing swapping). 190 * 191 * As with get_ptr(), this isn't actually virtual, but is instead to be 192 * defined in each final subclass. 193 */ 194 /* virtual char *get_writable_ptr(pool_ofs_t ofs) = 0; */ 195 196 /* 197 * Get the page size. This reflects the size of the pages in the 198 * backing store (usually the image file); this doesn't necessarily 199 * indicate anything about the way we manage the pool memory. 200 */ get_page_size()201 size_t get_page_size() const { return page_size_; } 202 203 /* get the number of pages in the pool */ 204 size_t get_page_count() const; 205 206 protected: 207 /* 208 * page size in bytes - this is simply the number of bytes on each page 209 * (each page in the pool has the same number of bytes) 210 */ 211 size_t page_size_; 212 213 /* backing store */ 214 class CVmPoolBackingStore *backing_store_; 215 216 /* our single contiguous allocation block */ 217 char *mem_; 218 }; 219 220 /* ------------------------------------------------------------------------ */ 221 /* 222 * "Flat" memory pool. This type of pool loads all pages into a single 223 * contiguous chunk of memory. This is suitable for platforms with large 224 * linear memory spaces, such as 32-bit platforms. 225 * 226 * This type of pool does not support dynamic allocation, so it's not 227 * suitable for use in a debugger build or other configurations that 228 * require dynamic allocation of pool space. 229 */ 230 class CVmPoolFlat: public CVmPool 231 { 232 public: CVmPoolFlat()233 CVmPoolFlat() 234 { 235 /* we don't have our memory chunk yet */ 236 mem_ = 0; 237 } 238 ~CVmPoolFlat(); 239 240 /* terminate - we don't need to do anything here */ terminate()241 void terminate() { } 242 243 /* attach to the backing store - loads all pages */ 244 void attach_backing_store(class CVmPoolBackingStore *backing_store); 245 246 /* detach from the backing store */ 247 void detach_backing_store(); 248 249 /* 250 * Translate an address. Since all of our memory is in one large 251 * contiguous chunk, this is extremely simple: just return the base of 252 * our memory block, offset by the pool offset. 253 */ get_ptr(pool_ofs_t ofs)254 inline const char *get_ptr(pool_ofs_t ofs) { return mem_ + ofs; } 255 256 /* we do not support writable pointers */ get_writable_ptr(pool_ofs_t ofs)257 inline char *get_writable_ptr(pool_ofs_t ofs) { return 0; } 258 }; 259 260 /* ------------------------------------------------------------------------ */ 261 /* 262 * Paged constant pool. 263 * 264 * This type of pool is divided into pages. A given object must be 265 * entirely contained in a single page. 266 * 267 * Each object is referenced by its address in the constant pool. An 268 * object address is simply an offset into the pool. 269 */ 270 class CVmPoolPaged: public CVmPool 271 { 272 public: 273 /* create the pool */ CVmPoolPaged()274 CVmPoolPaged() 275 { 276 /* no page slots allocated yet */ 277 pages_ = 0; 278 page_slots_ = 0; 279 page_slots_max_ = 0; 280 281 /* we don't have a backing store yet */ 282 backing_store_ = 0; 283 284 /* we don't know the page size yet */ 285 page_size_ = 0; 286 log2_page_size_ = 0; 287 } 288 289 /* 290 * Delete the pool. Call our non-virtual termination routine, as we 291 * can't use virtuals in destructors (not in the normal fashion, 292 * anyway). 293 */ ~CVmPoolPaged()294 virtual ~CVmPoolPaged() { terminate_nv(); } 295 296 /* delete everything in the pool using our base terminator routine */ terminate()297 virtual void terminate() { terminate_nv(); } 298 299 /* 300 * Attach to the given backing store to provide the the page data. 301 */ 302 virtual void 303 attach_backing_store(class CVmPoolBackingStore *backing_store); 304 305 protected: 306 /* non-virtual termination routine */ terminate_nv()307 void terminate_nv() 308 { 309 /* free our page memory */ 310 delete_page_list(); 311 } 312 313 /* delete our page list, if any */ 314 void delete_page_list(); 315 316 /* allocate or expand the page slot list */ 317 void alloc_page_slots(size_t slots); 318 319 /* 320 * Calculate which page we need, and the offset within the page, for 321 * a given pool offset. The page is the offset divided by the page 322 * size; since the page size is a power of two, this is simply a bit 323 * shift by log2(page_size). The page offset is the remainder after 324 * dividing the offset by the page size; again because the page size 325 * is a power of two, we can calculate this remainder simply by 326 * AND'ing the offset with the page size minus one. (Using these 327 * shift and mask operations may seem a little obscure, but it's so 328 * much faster on most machines than integer division that we're 329 * willing to be a little obscure in exchange for the performance 330 * gain.) 331 */ get_page_for_ofs(pool_ofs_t ofs)332 inline size_t get_page_for_ofs(pool_ofs_t ofs) const 333 { 334 return (size_t)(ofs >> log2_page_size_); 335 } 336 get_ofs_for_ofs(pool_ofs_t ofs)337 inline size_t get_ofs_for_ofs(pool_ofs_t ofs) const 338 { 339 return (size_t)(ofs & (page_size_ - 1)); 340 } 341 342 /* get the starting offset on the given page */ get_page_start_ofs(size_t pg)343 pool_ofs_t get_page_start_ofs(size_t pg) const 344 { 345 return ((pool_ofs_t)pg) << log2_page_size_; 346 } 347 348 /* 349 * The page list. This is an array of CVmPool_pg structures; each 350 * structure keeps track of one page in the pool. 351 * 352 * The page identified by the first page information structure contains 353 * pool offsets 0 through (page_size - 1); the next contains offsets 354 * page_size through (2*page_size - 1); and so on. 355 */ 356 CVmPool_pg *pages_; 357 358 /* 359 * The number of page slots in the page list. This starts at the 360 * initial page size and can grow dynamically as more pages are added. 361 */ 362 size_t page_slots_; 363 364 /* 365 * The maximum of allocated pages_ array entries. This might be larger 366 * than page_slots_, because we sometimes allocate more slots than we 367 * currently need to avoid having to allocate on every new page 368 * addition. 369 */ 370 size_t page_slots_max_; 371 372 /* log2 of the page size */ 373 int log2_page_size_; 374 }; 375 376 377 /* ------------------------------------------------------------------------ */ 378 /* 379 * Two-tiered paged pool. This is similar to the paged pool 380 * implementation, but uses a two-level page table: the first-level page 381 * table containers pointers to the second-level tables, and the 382 * second-level tables contain the pointers to the actual pages. 383 * 384 * This class is not currently used, because the two-level scheme isn't 385 * required in practice for modern machines and is less efficient than the 386 * single-level page table implemented in CVmPoolPaged. We retain this 387 * two-level code in case it's ever needed, though, because the two-level 388 * scheme might be useful for 16-bit segmented architectures. 389 * 390 * The advantage of the two-level scheme is that it allows very large 391 * memory spaces to be addressable without any single large allocations; 392 * the single-tier paged pool requires a single allocation equal to the 393 * total aggregate memory size divided by the page size times the size of a 394 * page pointer, which could be a fairly large single allocation for an 395 * extremely large aggregate pool size. However, it doesn't currently 396 * appear that the single-tier paging scheme will impose any limits that 397 * will be encountered in actual practice. 398 */ 399 #if 0 400 401 /* number of page information structures in each subarray */ 402 const size_t VMPOOL_SUBARRAY_SIZE = 4096; 403 404 class CVmPoolPaged2 405 { 406 public: 407 /* create the pool */ 408 CVmPoolPaged2() 409 { 410 /* no page slots allocated yet */ 411 pages_ = 0; 412 page_slots_ = 0; 413 414 /* we don't have a backing store yet */ 415 backing_store_ = 0; 416 417 /* we don't know the page size yet */ 418 page_size_ = 0; 419 log2_page_size_ = 0; 420 } 421 422 /* delete the pool */ 423 virtual ~CVmPoolPaged2(); 424 425 /* 426 * Attach to the given backing store to provide the the page data. 427 */ 428 virtual void 429 attach_backing_store(class CVmPoolBackingStore *backing_store); 430 431 protected: 432 /* delete our page list, if any */ 433 void delete_page_list(); 434 435 /* allocate or expand the page slot list */ 436 void alloc_page_slots(size_t slots); 437 438 /* 439 * Calculate which page we need, and the offset within the page, for a 440 * given pool offset. The page is the offset divided by the page size; 441 * since the page size is a power of two, this is simply a bit shift by 442 * log2(page_size). The page offset is the remainder after dividing 443 * the offset by the page size; again because the page size is a power 444 * of two, we can calculate this remainder simply by AND'ing the offset 445 * with the page size minus one. (Using these shift and mask 446 * operations may seem a little obscure, but it's so much faster on 447 * most machines than integer division that we're willing to be a 448 * little obscure in exchange for the performance gain.) 449 */ 450 inline size_t get_page_for_ofs(pool_ofs_t ofs) const 451 { 452 return (size_t)(ofs >> log2_page_size_); 453 } 454 455 inline size_t get_ofs_for_ofs(pool_ofs_t ofs) const 456 { 457 return (size_t)(ofs & (page_size_ - 1)); 458 } 459 460 /* get the starting offset on the given page */ 461 pool_ofs_t get_page_start_ofs(size_t pg) const 462 { 463 return ((pool_ofs_t)pg) << log2_page_size_; 464 } 465 466 /* get the number of subarrays */ 467 size_t get_subarray_count() const 468 { return ((page_slots_ + VMPOOL_SUBARRAY_SIZE - 1) 469 / VMPOOL_SUBARRAY_SIZE); } 470 471 /* get the page information structure for a given index */ 472 inline CVmPool_pg *get_page_info(size_t idx) const 473 { return &(pages_[idx / VMPOOL_SUBARRAY_SIZE] 474 [idx % VMPOOL_SUBARRAY_SIZE]); } 475 476 /* 477 * The page list. Each entry in this array is a subarray containing 478 * VMPOOL_SUBARRAY_SIZE page information structures, each of contains 479 * information on a page. Conceptually, the two-tiered array forms a 480 * single array; we keep two levels of arrays to accommodate 16-bit 481 * machines where a single large could be too large for a single 64k 482 * segment. 483 * 484 * The page identified by the first page information structure contains 485 * pool offsets 0 through (page_size - 1); the next contains offsets 486 * page_size through (2*page_size - 1); and so on. 487 */ 488 CVmPool_pg **pages_; 489 490 /* 491 * The number of slots allocated in the page list. This starts at 492 * the initial page size and can grow dynamically as more pages are 493 * added. 494 */ 495 size_t page_slots_; 496 497 /* log2 of the page size */ 498 int log2_page_size_; 499 }; 500 #endif /* 0 */ 501 502 /* ------------------------------------------------------------------------ */ 503 /* 504 * Dynamic pool manager interface. This is an abstract interface that 505 * provides a way to create new pool objects dynamically, and later 506 * delete those objects. 507 * 508 * Some types of pools support this interface, others do not. 509 */ 510 511 /* 512 * Dynamic pool object handle. Each object in a dynamic pool is 513 * identified by an object handle. When the dynpool_compress() method 514 * is called in the dynamic pool interface, the pool addresses of 515 * objects can change. 516 */ 517 class CVmPoolDynObj 518 { 519 public: CVmPoolDynObj(pool_ofs_t ofs,size_t len)520 CVmPoolDynObj(pool_ofs_t ofs, size_t len) 521 { 522 /* remember my location and size */ 523 ofs_ = ofs; 524 len_ = len; 525 526 /* not in a list yet */ 527 nxt_ = prv_ = 0; 528 529 /* presume it's in use */ 530 is_free_ = FALSE; 531 } 532 533 /* get/set the current pool address of this object */ get_ofs()534 pool_ofs_t get_ofs() const { return ofs_; } set_ofs(pool_ofs_t ofs)535 void set_ofs(pool_ofs_t ofs) { ofs_ = ofs; } 536 537 /* get/set my length */ get_len()538 size_t get_len() const { return len_; } set_len(size_t len)539 void set_len(size_t len) { len_ = len; } 540 541 /* get/set the next object in the list */ get_next()542 CVmPoolDynObj *get_next() const { return nxt_; } set_next(CVmPoolDynObj * obj)543 void set_next(CVmPoolDynObj *obj) { nxt_ = obj; } 544 545 /* get/set the previous object in the list */ get_prev()546 CVmPoolDynObj *get_prev() const { return prv_; } set_prev(CVmPoolDynObj * obj)547 void set_prev(CVmPoolDynObj *obj) { prv_ = obj; } 548 549 /* get/set the 'free' flag */ is_free()550 int is_free() const { return is_free_; } set_free(int f)551 void set_free(int f) { is_free_ = f; } 552 553 private: 554 /* my pool address */ 555 pool_ofs_t ofs_; 556 557 /* my length */ 558 size_t len_; 559 560 /* next/previous dynamic object in the list */ 561 CVmPoolDynObj *nxt_; 562 CVmPoolDynObj *prv_; 563 564 /* flag: this object's pool space is free */ 565 uint is_free_ : 1; 566 }; 567 568 /* 569 * dynamic pool manager interface 570 */ 571 class CVmPoolDynamic 572 { 573 public: 574 /* 575 * Allocate a new object in the pool. Returns a non-null object 576 * handle on success, or zero on failure. This can fail for 577 * different reasons: the object might be too large to fit in a 578 * single pool page, or there might be insufficient physical memory 579 * available. 580 */ 581 virtual CVmPoolDynObj *dynpool_alloc(size_t len) = 0; 582 583 /* 584 * Delete an object in the pool. 585 */ 586 virtual void dynpool_delete(CVmPoolDynObj *obj) = 0; 587 588 /* 589 * Compress the pool. To the extent possible, rearranges the 590 * dynamic objects in the pool to remove space left vacant by 591 * deleted objects. When this is called, the addresses of pool 592 * objects can change; this is the only time that addresses can 593 * change. This should be called after each batch of deletions to 594 * ensure that pool space is not wasted. (Deleting an object 595 * doesn't automatically compress the pool, so that a single 596 * compression pass can be made after a batch of deletions.) 597 */ 598 virtual void dynpool_compress() = 0; 599 }; 600 601 /* ------------------------------------------------------------------------ */ 602 /* 603 * In-memory pool implementation. This pool implementation pre-loads 604 * all available pages in the pool and keeps the complete pool in memory 605 * at all times. 606 */ 607 class CVmPoolInMem: public CVmPoolPaged, public CVmPoolDynamic 608 { 609 public: CVmPoolInMem()610 CVmPoolInMem() 611 { 612 /* no pages yet -> no dynamic pages */ 613 first_dyn_page_ = 0; 614 615 /* no dynamic objects yet */ 616 dyn_head_ = dyn_tail_ = 0; 617 } 618 619 /* 620 * delete - call our non-virtual terminator (use the non-virtual 621 * version, as this will just do our local termination; since we'll 622 * implicitly inherit the base class destructor, we don't want to 623 * explicitly inherit its termination as well) 624 */ ~CVmPoolInMem()625 ~CVmPoolInMem() { terminate_nv(); } 626 627 /* terminate */ terminate()628 void terminate() 629 { 630 /* call our own non-virtual termination routine */ 631 terminate_nv(); 632 633 /* inherit our base class handling */ 634 CVmPoolPaged::terminate(); 635 } 636 637 /* I provide a dynamic pool interface */ get_dynamic_ifc()638 virtual class CVmPoolDynamic *get_dynamic_ifc() { return this; } 639 640 /* attach to the backing store - loads all pages */ 641 void attach_backing_store(class CVmPoolBackingStore *backing_store); 642 643 /* detach from the backing store */ 644 void detach_backing_store(); 645 646 /* 647 * translate an address - since the pool is always in memory, we can 648 * translate an address simply by doing the arithmetic and finding 649 * the needed page, which is always loaded 650 */ get_ptr(pool_ofs_t ofs)651 inline const char *get_ptr(pool_ofs_t ofs) 652 { 653 /* translate the address through our page array */ 654 return (pages_[get_page_for_ofs(ofs)].mem + get_ofs_for_ofs(ofs)); 655 } 656 657 /* 658 * get a writable pointer - we allow write pointers as long as the 659 * backing store does 660 */ get_writable_ptr(pool_ofs_t ofs)661 inline char *get_writable_ptr(pool_ofs_t ofs) 662 { 663 /* 664 * If the backing store allows writing to its pages, allow 665 * writing. In any case, if the offset is in a dynamic page, we 666 * can always write to it, regardless of backing store policy, 667 * because we allocate and control the dynamic pages ourselves. 668 */ 669 if (backing_store_->vmpbs_is_writable() 670 || get_page_for_ofs(ofs) >= first_dyn_page_) 671 { 672 /* 673 * the backing store memory is writable - return a writable 674 * version of the normal pointer to this memory 675 */ 676 return (char *)get_ptr(ofs); 677 } 678 else 679 { 680 /* the backing store memory is non-writable - return failure */ 681 return 0; 682 } 683 } 684 685 /* 686 * dynamic pool interface 687 */ 688 689 /* allocate a dynamic object */ 690 virtual CVmPoolDynObj *dynpool_alloc(size_t len); 691 692 /* delete a dyanmic object */ 693 virtual void dynpool_delete(CVmPoolDynObj *obj); 694 695 /* compress the dynamic portion of the pool */ 696 virtual void dynpool_compress(); 697 698 private: 699 /* non-virtual termination */ 700 void terminate_nv(); 701 702 /* free any pages we allocated from the backing store */ 703 void free_backing_pages(); 704 705 /* add a dynamic handle at the end of the list */ 706 void append_dyn(CVmPoolDynObj *obj); 707 708 /* insert a dynamic handle after the given dynamic handle */ 709 void insert_dyn(CVmPoolDynObj *obj, CVmPoolDynObj *new_obj); 710 711 /* unlink a dynamic handle from the list */ 712 void unlink_dyn(CVmPoolDynObj *obj); 713 714 /* 715 * First dynamically-allocated page index - all pages from this page 716 * to the last page are dynamic. If this page index is equal to the 717 * total number of pages, there are no dynamic pages, since this 718 * index refers to an invalid page. 719 */ 720 size_t first_dyn_page_; 721 722 /* head and tail of list of dynamic pool objects */ 723 CVmPoolDynObj *dyn_head_; 724 CVmPoolDynObj *dyn_tail_; 725 }; 726 727 #endif /* VMPOOL_H */ 728 729