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