memory/global.c

   1 static char RCSId[] = "$Id: global.c,v 1.2 1993/07/04 04:04:21 root Exp root $";
   2 static char Copyright[] = "Copyright  Robert J. Amstadt, 1993";
   3
   4 #include <stdio.h>
   5 #include <stdlib.h>
   6 #include "prototypes.h"
   7 #include "heap.h"
   8 #include "segmem.h"
   9
  10 /*
  11  * Global memory pool descriptor.  Segments MUST be maintained in segment
  12  * ascending order.  If not the reallocation routine will die a horrible
  13  * death.
  14  *
  15  * handle  = 0, this descriptor contains the address of a free pool.
  16  *        != 0, this describes an allocated block.
  17  *
  18  * sequence = 0, this is not a huge block
  19  *          > 0, this is a portion of a huge block
  20  *          =-1, this is a free segment
  21  *
  22  * addr       - address of this memory block.
  23  *
  24  * length     - used to maintain huge blocks.
  25  *
  26  */
  27 typedef struct global_mem_desc_s
  28 {
  29     struct global_mem_desc_s *next;
  30     struct global_mem_desc_s *prev;
  31     unsigned short handle;
  32     short sequence;
  33     void *addr;
  34     int length;
  35     int lock_count;
  36 } GDESC;
  37
  38 GDESC *GlobalList = NULL;
  39 static unsigned short next_unused_handle = 1;
  40
  41 \f
  42 /**********************************************************************
  43  *                                      GlobalGetFreeSegments
  44  */
  45 GDESC *
  46 GlobalGetFreeSegments(unsigned int flags, int n_segments)
  47 {
  48     struct segment_descriptor_s *s;
  49     GDESC *g;
  50     GDESC *g_start;
  51     GDESC *g_prev;
  52     int count, i;
  53
  54     /*
  55      * Try to find some empty segments in our list.
  56      */
  57     count = 0;
  58     for (g = GlobalList; g != NULL && count != n_segments; g = g->next)
  59     {
  60         if ((int) g->sequence == -1)
  61         {
  62             if (count > 0)
  63             {
  64                 if (g->prev->handle + 8 != g->handle)
  65                     count = 0;
  66                 else
  67                     count++;
  68             }
  69             else
  70             {
  71                 g_start = g;
  72                 count = 1;
  73             }
  74         }
  75         else if (count)
  76             count = 0;
  77     }
  78
  79     /*
  80      * If we couldn't find enough segments, then we need to create some.
  81      */
  82     if (count != n_segments)
  83     {
  84         /*
  85          * Find list tail.
  86          */
  87         g_prev = NULL;
  88         for (g = GlobalList; g != NULL; g = g->next)
  89             g_prev = g;
  90
  91         /*
  92          * Allocate segments.
  93          */
  94         for (count = 0; count < n_segments; count++)
  95         {
  96             s = GetNextSegment(flags, 0x10000);
  97             if (s == NULL) {
  98                 printf("GlobalGetFreeSegments // bad GetNextSegment !\n");
  99                 return NULL;
 100                 }
 101             g = (GDESC *) malloc(sizeof(*g));
 102             if (g == NULL) {
 103                 printf("GlobalGetFreeSegments // bad GDESC malloc !\n");
 104                 return NULL;
 105                 }
 106             g->prev = g_prev;
 107             g->next = NULL;
 108             g->handle = s->selector;
 109             g->sequence = -1;
 110             g->addr = s->base_addr;
 111             g->length = s->length;
 112             if (!(flags & GLOBAL_FLAGS_MOVEABLE))
 113                 g->lock_count = 1;
 114             else
 115                 g->lock_count = 0;
 116
 117             if (count == 0) g_start = g;
 118
 119             if (g_prev != NULL)
 120             {
 121                 g_prev->next = g;
 122             }
 123             else
 124                 GlobalList = g;
 125             g_prev = g;
 126         }
 127     }
 128
 129     /*
 130      * We have all of the segments we need.  Let's adjust their contents.
 131      */
 132     g = g_start;
 133     for (i = 0; i < n_segments; i++, g = g->next)
 134     {
 135         if (g == NULL) {
 136             printf("GlobalGetFreeSegments // bad Segments chain !\n");
 137             return NULL;
 138             }
 139         g->sequence = i + 1;
 140         g->length = n_segments;
 141     }
 142
 143     return g_start;
 144 }
 145 \f
 146 /**********************************************************************
 147  *                                      GlobalAlloc
 148  */
 149 unsigned int
 150 GlobalAlloc(unsigned int flags, unsigned long size)
 151 {
 152     GDESC *g;
 153     GDESC *g_prev;
 154     void *m;
 155
 156     /*
 157      * If this block is fixed or very big we need to allocate entire
 158      * segments.
 159      */
 160     if (size > 0x8000 || !(flags & GLOBAL_FLAGS_MOVEABLE))
 161     {
 162         int segments = (size >> 16) + 1;
 163
 164         g = GlobalGetFreeSegments(flags, segments);
 165         if (g == NULL)
 166             return 0;
 167         else
 168             return g->handle;
 169     }
 170     /*
 171      * Otherwise we just need a little piece of a segment.
 172      */
 173     else
 174     {
 175         /*
 176          * Try to allocate from active free lists.
 177          */
 178         for (g = GlobalList; g != NULL; g = g->next)
 179         {
 180             if (g->handle == 0 && g->sequence == 0)
 181             {
 182                 m = HEAP_Alloc((MDESC **) g->addr, 0, size);
 183                 if (m != NULL)
 184                     break;
 185             }
 186         }
 187
 188         /*
 189          * If we couldn't get the memory there, then we need to create
 190          * a new free list.
 191          */
 192         if (g == NULL)
 193         {
 194             g = GlobalGetFreeSegments(0, 1);
 195             if (g == NULL)
 196                 return 0;
 197
 198             g->handle = 0;
 199             g->sequence = 0;
 200             HEAP_Init((MDESC **) g->addr, (MDESC **) g->addr + 1,
 201                       0x10000 - sizeof(MDESC **));
 202             m = HEAP_Alloc((MDESC **) g->addr, flags & GLOBAL_FLAGS_ZEROINIT,
 203                            size);
 204             if (m == NULL)
 205                 return 0;
 206         }
 207
 208         /*
 209          * Save position of heap descriptor.
 210          */
 211         g_prev = g;
 212
 213         /*
 214          * We have a new block.  Let's create a GDESC entry for it.
 215          */
 216         g = malloc(sizeof(*g));
 217 #ifdef DEBUG_HEAP
 218         printf("New GDESC %08x\n", g);
 219 #endif
 220         if (g == NULL)
 221             return 0;
 222
 223         g->handle = next_unused_handle;
 224         g->sequence = 0;
 225         g->addr = m;
 226         g->length = size;
 227         g->next = g_prev->next;
 228         if (g->next) g->next->prev = g;
 229         g->lock_count = 0;
 230
 231         g_prev->next = g;
 232         g->prev = g_prev;
 233
 234         next_unused_handle++;
 235         if ((next_unused_handle & 7) == 7)
 236             next_unused_handle++;
 237
 238 #ifdef DEBUG_HEAP
 239         printf("GlobalAlloc: returning %04x\n", g->handle);
 240 #endif
 241         return g->handle;
 242     }
 243 }
 244 \f
 245 /**********************************************************************
 246  *                                      GlobalFree
 247  *
 248  * Windows programs will pass a handle in the "block" parameter, but
 249  * this function will also accept a 32-bit address.
 250  */
 251 unsigned int
 252 GlobalFree(unsigned int block)
 253 {
 254     GDESC *g;
 255
 256     if (block == 0)
 257         return 0;
 258
 259     /*
 260      * Find GDESC for this block.
 261      */
 262     if (block & 0xffff0000)
 263     {
 264         for (g = GlobalList; g != NULL; g = g->next)
 265             if (g->handle > 0 && (unsigned int) g->addr == block)
 266                 break;
 267     }
 268     else
 269     {
 270         for (g = GlobalList; g != NULL; g = g->next)
 271             if (g->handle == block)
 272                 break;
 273     }
 274     if (g == NULL)
 275         return block;
 276
 277     /*
 278      * If the sequence number is zero then use HEAP_Free to deallocate
 279      * memory, and throw away this descriptor.
 280      */
 281     if (g->sequence == 0)
 282     {
 283         HEAP_Free((MDESC **) ((int) g->addr & 0xffff0000), (void *) g->addr);
 284
 285         g->prev->next = g->next;
 286
 287         if (g->next != NULL)
 288             g->next->prev = g->prev;
 289
 290         free(g);
 291     }
 292
 293     /*
 294      * Otherwise just mark these descriptors as free.
 295      */
 296     else
 297     {
 298         int i, limit;
 299
 300         limit = g->length;
 301         for (i = g->sequence - 1; i < limit && g != NULL; i++, g = g->next)
 302         {
 303             g->sequence = -1;
 304             g->length = 0x10000;
 305         }
 306     }
 307
 308     return 0;
 309 }
 310 \f
 311 /**********************************************************************
 312  *                                      GlobalLock
 313  *
 314  */
 315 void *
 316 GlobalLock(unsigned int block)
 317 {
 318     GDESC *g;
 319
 320     if (block == 0)
 321         return 0;
 322
 323     /*
 324      * Find GDESC for this block.
 325      */
 326     for (g = GlobalList; g != NULL; g = g->next)
 327     {
 328         if (g->handle == block)
 329         {
 330             g->lock_count++;
 331 #ifdef DEBUG_HEAP
 332             printf("GlobalLock: returning %08x\n", g->addr);
 333 #endif
 334             return g->addr;
 335         }
 336     }
 337
 338 #ifdef DEBUG_HEAP
 339     printf("GlobalLock: returning %08x\n", 0);
 340 #endif
 341     return NULL;
 342 }
 343 \f
 344 /**********************************************************************
 345  *                                      GlobalUnlock
 346  *
 347  */
 348 int
 349 GlobalUnlock(unsigned int block)
 350 {
 351     GDESC *g;
 352
 353     if (block == 0)
 354         return 0;
 355
 356     /*
 357      * Find GDESC for this block.
 358      */
 359     for (g = GlobalList; g != NULL; g = g->next)
 360     {
 361         if (g->handle == block && g->lock_count > 0)
 362         {
 363             g->lock_count--;
 364             return 0;
 365         }
 366     }
 367
 368     return 1;
 369 }
 370 \f
 371 /**********************************************************************
 372  *                                      GlobalFlags
 373  *
 374  */
 375 unsigned int
 376 GlobalFlags(unsigned int block)
 377 {
 378     GDESC *g;
 379
 380     if (block == 0)
 381         return 0;
 382
 383     /*
 384      * Find GDESC for this block.
 385      */
 386     for (g = GlobalList; g != NULL; g = g->next)
 387     {
 388         if (g->handle == block)
 389             return g->lock_count;
 390     }
 391
 392     return 0;
 393 }
 394 \f
 395 /**********************************************************************
 396  *                                      GlobalSize
 397  *
 398  */
 399 unsigned int
 400 GlobalSize(unsigned int block)
 401 {
 402     GDESC *g;
 403
 404     if (block == 0)
 405         return 0;
 406
 407     /*
 408      * Find GDESC for this block.
 409      */
 410     for (g = GlobalList; g != NULL; g = g->next)
 411     {
 412         if (g->handle == block)
 413             return g->length;
 414     }
 415
 416     return 0;
 417 }
 418 \f
 419 /**********************************************************************
 420  *                                      GlobalHandle
 421  *
 422  * This routine is not strictly correct.  MS Windows creates a selector
 423  * for every locked global block.  We do not.  If the allocation is small
 424  * enough, we only give out a little piece of a selector.  Thus this
 425  * function cannot be implemented.
 426  */
 427 unsigned int
 428 GlobalHandle(unsigned int selector)
 429 {
 430     GDESC *g;
 431
 432     if (selector == 0)
 433         return 0;
 434
 435     /*
 436      * Find GDESC for this block.
 437      */
 438     for (g = GlobalList; g != NULL; g = g->next)
 439     {
 440         if (g->handle == selector)
 441         {
 442             if (g->sequence > 0)
 443                 return g->handle;
 444             else
 445             {
 446                 fprintf(stderr, "Attempt to get a handle "
 447                         "from a selector to a far heap.\n");
 448                 return 0;
 449             }
 450         }
 451     }
 452
 453     return 0;
 454 }
 455 \f
 456 /**********************************************************************
 457  *                                      GlobalCompact
 458  *
 459  */
 460 unsigned int
 461 GlobalCompact(unsigned int desired)
 462 {
 463     GDESC *g;
 464     unsigned char free_map[512];
 465     unsigned int max_selector_used = 0;
 466     unsigned int i;
 467     unsigned int selector;
 468     int current_free;
 469     int max_free;
 470
 471     /*
 472      * Initialize free list to all items not controlled by GlobalAlloc()
 473      */
 474     for (i = 0; i < 512; i++)
 475         free_map[i] = -1;
 476
 477     /*
 478      * Traverse table looking for used and free selectors.
 479      */
 480     for (g = GlobalList; g != NULL; g = g->next)
 481     {
 482         /*
 483          * Check for free segments.
 484          */
 485         if (g->sequence == -1)
 486         {
 487             free_map[g->handle >> 3] = 1;
 488             if (g->handle > max_selector_used)
 489                 max_selector_used = g->handle;
 490         }
 491
 492         /*
 493          * Check for heap allocated segments.
 494          */
 495         else if (g->handle == 0)
 496         {
 497             selector = (unsigned int) g->addr >> 16;
 498             free_map[selector >> 3] = 0;
 499             if (selector > max_selector_used)
 500                 max_selector_used = selector;
 501         }
 502     }
 503
 504     /*
 505      * All segments past the biggest selector used are free.
 506      */
 507     for (i = (max_selector_used >> 3) + 1; i < 512; i++)
 508         free_map[i] = 1;
 509
 510     /*
 511      * Find the largest free block of segments
 512      */
 513     current_free = 0;
 514     max_free = 0;
 515     for (i = 0; i < 512; i++)
 516     {
 517         if (free_map[i] == 1)
 518         {
 519             current_free++;
 520         }
 521         else
 522         {
 523             if (current_free > max_free)
 524                 max_free = current_free;
 525             current_free = 0;
 526         }
 527     }
 528
 529     return max_free << 16;
 530 }
 531 \f
 532 /**********************************************************************
 533  *                                      GlobalReAlloc
 534  *
 535  */
 536 unsigned int
 537 GlobalReAlloc(unsigned int block, unsigned int new_size, unsigned int flags)
 538 {
 539     GDESC *g;
 540     unsigned int n_segments;
 541     int i;
 542
 543     if (block == 0)
 544         return 0;
 545
 546     /*
 547      * Find GDESC for this block.
 548      */
 549     for (g = GlobalList; g != NULL; g = g->next)
 550     {
 551         if (g->handle == block)
 552             break;
 553     }
 554
 555     if (g == NULL)
 556         return 0;
 557
 558     /*
 559      * If this is a heap allocated block,  then use HEAP_ReAlloc() to
 560      * reallocate the block.  If this fails, call GlobalAlloc() to get
 561      * a new block.
 562      */
 563     if (g->sequence == 0)
 564     {
 565         MDESC **free_list;
 566         void *p;
 567
 568         free_list = (MDESC **) ((unsigned int) g->addr & 0xffff0000);
 569         p = HEAP_ReAlloc(free_list, g->addr, new_size, flags) ;
 570         if (p == NULL)
 571         {
 572             unsigned int handle = GlobalAlloc(flags, new_size);
 573             if (handle == 0)
 574                 return 0;
 575             p = GlobalLock(handle);
 576             memcpy(p, g->addr, g->length);
 577             GlobalUnlock(handle);
 578             GlobalFree(g->handle);
 579
 580             return handle;
 581         }
 582         else
 583         {
 584             g->addr = p;
 585             g->length = new_size;
 586             return g->handle;
 587         }
 588     }
 589
 590     /*
 591      * Otherwise, we need to do the work ourselves.  First verify the
 592      * handle.
 593      */
 594     else
 595     {
 596         if (g->sequence != 1)
 597             return 0;
 598
 599         /*
 600          * Do we need more memory?  Segments are in ascending order in
 601          * the GDESC list.
 602          */
 603         n_segments = (new_size >> 16) + 1;
 604         if (n_segments > g->length)
 605         {
 606             GDESC *g_new;
 607             GDESC *g_start = g;
 608             int old_segments = g_start->length;
 609             unsigned short next_handle = g_start->handle;
 610
 611             for (i = 1; i <= n_segments; i++, g = g->next)
 612             {
 613                 /*
 614                  * If we run into a block allocated to something else,
 615                  * try GlobalGetFreeSegments() and memcpy(). (Yuk!)
 616                  */
 617                 if (g->sequence != i || g->handle != next_handle)
 618                 {
 619                     g = GlobalGetFreeSegments(flags, n_segments);
 620                     if (g == NULL)
 621                         return 0;
 622
 623                     memcpy(g->addr, g_start->addr,
 624                            g_start->length << 16);
 625
 626                     GlobalFree(block);
 627                     return g->handle;
 628                 }
 629
 630                 /*
 631                  * Otherwise this block is used by us or free.  So,
 632                  * snatch it.  If this block is new and we are supposed to
 633                  * zero init, then do some erasing.
 634                  */
 635                 if (g->sequence == -1 && (flags & GLOBAL_FLAGS_ZEROINIT))
 636                     memset(g->addr, 0, 0x10000);
 637
 638                 g->sequence = i;
 639                 g->length = n_segments;
 640                 next_handle += 8;
 641
 642                 /*
 643                  * If the next descriptor is non-existant, then use
 644                  * GlobalGetFreeSegments to create them.
 645                  */
 646                 if (i != n_segments && g->next == NULL)
 647                 {
 648                     g_new = GlobalGetFreeSegments(flags, n_segments - i);
 649                     if (g_new == NULL)
 650                         return 0;
 651                     GlobalFree(g_new->handle);
 652                 }
 653             }
 654
 655             return g_start->handle;
 656         }
 657
 658         /*
 659          * Do we need less memory?
 660          */
 661         else if (n_segments < g->length)
 662         {
 663             GDESC *g_free;
 664
 665             g_free = g;
 666             for (i = 0; i < n_segments; i++)
 667             {
 668                 if (g_free->sequence != i + 1)
 669                     return 0;
 670                 g_free = g_free->next;
 671             }
 672         }
 673
 674         /*
 675          * We already have exactly the right amount of memory.
 676          */
 677         else
 678             return block;
 679     }
 680
 681     /*
 682      * If we fall through it must be an error.
 683      */
 684     return 0;
 685 }
 686 \f
 687 /**********************************************************************
 688  *                                      GlobalQuickAlloc
 689  */
 690 void *
 691 GlobalQuickAlloc(int size)
 692 {
 693     unsigned int hmem;
 694
 695     hmem = GlobalAlloc(GLOBAL_FLAGS_MOVEABLE, size);
 696     if (hmem == 0)
 697         return NULL;
 698     else
 699         return GlobalLock(hmem);
 700 }
 701 \f
 702 /**********************************************************************
 703  *                                      GlobalHandleFromPointer
 704
 705  */
 706 unsigned int
 707 GlobalHandleFromPointer(void *block)
 708 {
 709     GDESC *g;
 710
 711     if (block == NULL)
 712         return 0;
 713
 714     /*
 715      * Find GDESC for this block.
 716      */
 717     for (g = GlobalList; g != NULL; g = g->next)
 718         if (g->handle > 0 && g->addr == block)
 719             break;
 720
 721     if (g == NULL)
 722         return 0;
 723     else
 724         return g->handle;
 725 }
 726
 727
 728