qemu/roms/seabios/src/malloc.c

   1 // Internal dynamic memory allocations.
   2 //
   3 // Copyright (C) 2009-2013  Kevin O'Connor <kevin@koconnor.net>
   4 //
   5 // This file may be distributed under the terms of the GNU LGPLv3 license.
   6
   7 #include "biosvar.h" // GET_BDA
   8 #include "config.h" // BUILD_BIOS_ADDR
   9 #include "list.h" // hlist_node
  10 #include "malloc.h" // _malloc
  11 #include "memmap.h" // struct e820entry
  12 #include "output.h" // dprintf
  13 #include "stacks.h" // wait_preempt
  14 #include "std/optionrom.h" // OPTION_ROM_ALIGN
  15 #include "string.h" // memset
  16
  17 // Information on a reserved area.
  18 struct allocinfo_s {
  19     struct hlist_node node;
  20     void *data, *dataend, *allocend;
  21 };
  22
  23 // Information on a tracked memory allocation.
  24 struct allocdetail_s {
  25     struct allocinfo_s detailinfo;
  26     struct allocinfo_s datainfo;
  27     u32 handle;
  28 };
  29
  30 // The various memory zones.
  31 struct zone_s {
  32     struct hlist_head head;
  33 };
  34
  35 struct zone_s ZoneLow VARVERIFY32INIT, ZoneHigh VARVERIFY32INIT;
  36 struct zone_s ZoneFSeg VARVERIFY32INIT;
  37 struct zone_s ZoneTmpLow VARVERIFY32INIT, ZoneTmpHigh VARVERIFY32INIT;
  38
  39 static struct zone_s *Zones[] VARVERIFY32INIT = {
  40     &ZoneTmpLow, &ZoneLow, &ZoneFSeg, &ZoneTmpHigh, &ZoneHigh
  41 };
  42
  43
  44 /****************************************************************
  45  * low-level memory reservations
  46  ****************************************************************/
  47
  48 // Find and reserve space from a given zone
  49 static void *
  50 allocSpace(struct zone_s *zone, u32 size, u32 align, struct allocinfo_s *fill)
  51 {
  52     struct allocinfo_s *info;
  53     hlist_for_each_entry(info, &zone->head, node) {
  54         void *dataend = info->dataend;
  55         void *allocend = info->allocend;
  56         void *newallocend = (void*)ALIGN_DOWN((u32)allocend - size, align);
  57         if (newallocend >= dataend && newallocend <= allocend) {
  58             // Found space - now reserve it.
  59             if (!fill)
  60                 fill = newallocend;
  61             fill->data = newallocend;
  62             fill->dataend = newallocend + size;
  63             fill->allocend = allocend;
  64
  65             info->allocend = newallocend;
  66             hlist_add_before(&fill->node, &info->node);
  67             return newallocend;
  68         }
  69     }
  70     return NULL;
  71 }
  72
  73 // Release space allocated with allocSpace()
  74 static void
  75 freeSpace(struct allocinfo_s *info)
  76 {
  77     struct allocinfo_s *next = container_of_or_null(
  78         info->node.next, struct allocinfo_s, node);
  79     if (next && next->allocend == info->data)
  80         next->allocend = info->allocend;
  81     hlist_del(&info->node);
  82 }
  83
  84 // Add new memory to a zone
  85 static void
  86 addSpace(struct zone_s *zone, void *start, void *end)
  87 {
  88     // Find position to add space
  89     struct allocinfo_s *info;
  90     struct hlist_node **pprev;
  91     hlist_for_each_entry_pprev(info, pprev, &zone->head, node) {
  92         if (info->data < start)
  93             break;
  94     }
  95
  96     // Add space using temporary allocation info.
  97     struct allocdetail_s tempdetail;
  98     tempdetail.datainfo.data = tempdetail.datainfo.dataend = start;
  99     tempdetail.datainfo.allocend = end;
 100     hlist_add(&tempdetail.datainfo.node, pprev);
 101
 102     // Allocate final allocation info.
 103     struct allocdetail_s *detail = allocSpace(
 104         &ZoneTmpHigh, sizeof(*detail), MALLOC_MIN_ALIGN, NULL);
 105     if (!detail) {
 106         detail = allocSpace(&ZoneTmpLow, sizeof(*detail)
 107                             , MALLOC_MIN_ALIGN, NULL);
 108         if (!detail) {
 109             hlist_del(&tempdetail.datainfo.node);
 110             warn_noalloc();
 111             return;
 112         }
 113     }
 114
 115     // Replace temp alloc space with final alloc space
 116     pprev = tempdetail.datainfo.node.pprev;
 117     hlist_del(&tempdetail.datainfo.node);
 118     memcpy(&detail->datainfo, &tempdetail.datainfo, sizeof(detail->datainfo));
 119     detail->handle = MALLOC_DEFAULT_HANDLE;
 120     hlist_add(&detail->datainfo.node, pprev);
 121 }
 122
 123 // Search all zones for an allocation obtained from allocSpace()
 124 static struct allocinfo_s *
 125 findAlloc(void *data)
 126 {
 127     int i;
 128     for (i=0; i<ARRAY_SIZE(Zones); i++) {
 129         struct allocinfo_s *info;
 130         hlist_for_each_entry(info, &Zones[i]->head, node) {
 131             if (info->data == data)
 132                 return info;
 133         }
 134     }
 135     return NULL;
 136 }
 137
 138 // Return the last sentinal node of a zone
 139 static struct allocinfo_s *
 140 findLast(struct zone_s *zone)
 141 {
 142     struct allocinfo_s *info, *last = NULL;
 143     hlist_for_each_entry(info, &zone->head, node) {
 144         last = info;
 145     }
 146     return last;
 147 }
 148
 149
 150 /****************************************************************
 151  * ebda movement
 152  ****************************************************************/
 153
 154 // Move ebda
 155 static int
 156 relocate_ebda(u32 newebda, u32 oldebda, u8 ebda_size)
 157 {
 158     u32 lowram = GET_BDA(mem_size_kb) * 1024;
 159     if (oldebda != lowram)
 160         // EBDA isn't at end of ram - give up.
 161         return -1;
 162
 163     // Do copy
 164     memmove((void*)newebda, (void*)oldebda, ebda_size * 1024);
 165
 166     // Update indexes
 167     dprintf(1, "ebda moved from %x to %x\n", oldebda, newebda);
 168     SET_BDA(mem_size_kb, newebda / 1024);
 169     SET_BDA(ebda_seg, FLATPTR_TO_SEG(newebda));
 170     return 0;
 171 }
 172
 173 // Support expanding the ZoneLow dynamically.
 174 static void *
 175 zonelow_expand(u32 size, u32 align, struct allocinfo_s *fill)
 176 {
 177     // Make sure to not move ebda while an optionrom is running.
 178     if (unlikely(wait_preempt())) {
 179         void *data = allocSpace(&ZoneLow, size, align, fill);
 180         if (data)
 181             return data;
 182     }
 183
 184     struct allocinfo_s *info = findLast(&ZoneLow);
 185     if (!info)
 186         return NULL;
 187     u32 oldpos = (u32)info->allocend;
 188     u32 newpos = ALIGN_DOWN(oldpos - size, align);
 189     u32 bottom = (u32)info->dataend;
 190     if (newpos >= bottom && newpos <= oldpos)
 191         // Space already present.
 192         return allocSpace(&ZoneLow, size, align, fill);
 193     u16 ebda_seg = get_ebda_seg();
 194     u32 ebda_pos = (u32)MAKE_FLATPTR(ebda_seg, 0);
 195     u8 ebda_size = GET_EBDA(ebda_seg, size);
 196     u32 ebda_end = ebda_pos + ebda_size * 1024;
 197     if (ebda_end != bottom)
 198         // Something else is after ebda - can't use any existing space.
 199         newpos = ALIGN_DOWN(ebda_end - size, align);
 200     u32 newbottom = ALIGN_DOWN(newpos, 1024);
 201     u32 newebda = ALIGN_DOWN(newbottom - ebda_size * 1024, 1024);
 202     if (newebda < BUILD_EBDA_MINIMUM)
 203         // Not enough space.
 204         return NULL;
 205
 206     // Move ebda
 207     int ret = relocate_ebda(newebda, ebda_pos, ebda_size);
 208     if (ret)
 209         return NULL;
 210
 211     // Update zone
 212     if (ebda_end == bottom) {
 213         info->data = (void*)newbottom;
 214         info->dataend = (void*)newbottom;
 215     } else
 216         addSpace(&ZoneLow, (void*)newbottom, (void*)ebda_end);
 217
 218     return allocSpace(&ZoneLow, size, align, fill);
 219 }
 220
 221
 222 /****************************************************************
 223  * tracked memory allocations
 224  ****************************************************************/
 225
 226 // Allocate memory from the given zone and track it as a PMM allocation
 227 void * __malloc
 228 _malloc(struct zone_s *zone, u32 size, u32 align)
 229 {
 230     ASSERT32FLAT();
 231     if (!size)
 232         return NULL;
 233
 234     // Find and reserve space for bookkeeping.
 235     struct allocdetail_s *detail = allocSpace(
 236         &ZoneTmpHigh, sizeof(*detail), MALLOC_MIN_ALIGN, NULL);
 237     if (!detail) {
 238         detail = allocSpace(&ZoneTmpLow, sizeof(*detail)
 239                             , MALLOC_MIN_ALIGN, NULL);
 240         if (!detail)
 241             return NULL;
 242     }
 243     detail->handle = MALLOC_DEFAULT_HANDLE;
 244
 245     // Find and reserve space for main allocation
 246     void *data = allocSpace(zone, size, align, &detail->datainfo);
 247     if (!CONFIG_MALLOC_UPPERMEMORY && !data && zone == &ZoneLow)
 248         data = zonelow_expand(size, align, &detail->datainfo);
 249     if (!data) {
 250         freeSpace(&detail->detailinfo);
 251         return NULL;
 252     }
 253
 254     dprintf(8, "_malloc zone=%p size=%d align=%x ret=%p (detail=%p)\n"
 255             , zone, size, align, data, detail);
 256
 257     return data;
 258 }
 259
 260 // Free a data block allocated with _malloc
 261 int
 262 _free(void *data)
 263 {
 264     ASSERT32FLAT();
 265     struct allocinfo_s *info = findAlloc(data);
 266     if (!info || data == (void*)info || data == info->dataend)
 267         return -1;
 268     struct allocdetail_s *detail = container_of(
 269         info, struct allocdetail_s, datainfo);
 270     dprintf(8, "_free %p (detail=%p)\n", data, detail);
 271     freeSpace(info);
 272     freeSpace(&detail->detailinfo);
 273     return 0;
 274 }
 275
 276 // Find the amount of free space in a given zone.
 277 u32
 278 malloc_getspace(struct zone_s *zone)
 279 {
 280     // XXX - doesn't account for ZoneLow being able to grow.
 281     // XXX - results not reliable when CONFIG_THREAD_OPTIONROMS
 282     u32 maxspace = 0;
 283     struct allocinfo_s *info;
 284     hlist_for_each_entry(info, &zone->head, node) {
 285         u32 space = info->allocend - info->dataend;
 286         if (space > maxspace)
 287             maxspace = space;
 288     }
 289
 290     if (zone != &ZoneTmpHigh && zone != &ZoneTmpLow)
 291         return maxspace;
 292     // Account for space needed for PMM tracking.
 293     u32 reserve = ALIGN(sizeof(struct allocdetail_s), MALLOC_MIN_ALIGN);
 294     if (maxspace <= reserve)
 295         return 0;
 296     return maxspace - reserve;
 297 }
 298
 299 // Set a handle associated with an allocation.
 300 void
 301 malloc_sethandle(void *data, u32 handle)
 302 {
 303     ASSERT32FLAT();
 304     struct allocinfo_s *info = findAlloc(data);
 305     if (!info || data == (void*)info || data == info->dataend)
 306         return;
 307     struct allocdetail_s *detail = container_of(
 308         info, struct allocdetail_s, datainfo);
 309     detail->handle = handle;
 310 }
 311
 312 // Find the data block allocated with _malloc with a given handle.
 313 void *
 314 malloc_findhandle(u32 handle)
 315 {
 316     int i;
 317     for (i=0; i<ARRAY_SIZE(Zones); i++) {
 318         struct allocinfo_s *info;
 319         hlist_for_each_entry(info, &Zones[i]->head, node) {
 320             if (info->data != (void*)info)
 321                 continue;
 322             struct allocdetail_s *detail = container_of(
 323                 info, struct allocdetail_s, detailinfo);
 324             if (detail->handle == handle)
 325                 return detail->datainfo.data;
 326         }
 327     }
 328     return NULL;
 329 }
 330
 331
 332 /****************************************************************
 333  * 0xc0000-0xf0000 management
 334  ****************************************************************/
 335
 336 static u32 RomEnd = BUILD_ROM_START;
 337 static struct allocinfo_s *RomBase;
 338
 339 #define OPROM_HEADER_RESERVE 16
 340
 341 // Return the maximum memory position option roms may use.
 342 u32
 343 rom_get_max(void)
 344 {
 345     if (CONFIG_MALLOC_UPPERMEMORY)
 346         return ALIGN_DOWN((u32)RomBase->allocend - OPROM_HEADER_RESERVE
 347                           , OPTION_ROM_ALIGN);
 348     extern u8 final_readonly_start[];
 349     return (u32)final_readonly_start;
 350 }
 351
 352 // Return the end of the last deployed option rom.
 353 u32
 354 rom_get_last(void)
 355 {
 356     return RomEnd;
 357 }
 358
 359 // Request space for an optionrom in 0xc0000-0xf0000 area.
 360 struct rom_header *
 361 rom_reserve(u32 size)
 362 {
 363     u32 newend = ALIGN(RomEnd + size, OPTION_ROM_ALIGN);
 364     if (newend > rom_get_max())
 365         return NULL;
 366     if (CONFIG_MALLOC_UPPERMEMORY) {
 367         if (newend < (u32)zonelow_base)
 368             newend = (u32)zonelow_base;
 369         RomBase->data = RomBase->dataend = (void*)newend + OPROM_HEADER_RESERVE;
 370     }
 371     return (void*)RomEnd;
 372 }
 373
 374 // Confirm space as in use by an optionrom.
 375 int
 376 rom_confirm(u32 size)
 377 {
 378     void *new = rom_reserve(size);
 379     if (!new) {
 380         warn_noalloc();
 381         return -1;
 382     }
 383     RomEnd = ALIGN(RomEnd + size, OPTION_ROM_ALIGN);
 384     return 0;
 385 }
 386
 387
 388 /****************************************************************
 389  * Setup
 390  ****************************************************************/
 391
 392 void
 393 malloc_preinit(void)
 394 {
 395     ASSERT32FLAT();
 396     dprintf(3, "malloc preinit\n");
 397
 398     // Don't declare any memory between 0xa0000 and 0x100000
 399     add_e820(BUILD_LOWRAM_END, BUILD_BIOS_ADDR-BUILD_LOWRAM_END, E820_HOLE);
 400
 401     // Mark known areas as reserved.
 402     add_e820(BUILD_BIOS_ADDR, BUILD_BIOS_SIZE, E820_RESERVED);
 403
 404     // Populate temp high ram
 405     u32 highram = 0;
 406     int i;
 407     for (i=e820_count-1; i>=0; i--) {
 408         struct e820entry *en = &e820_list[i];
 409         u64 end = en->start + en->size;
 410         if (end < 1024*1024)
 411             break;
 412         if (en->type != E820_RAM || end > 0xffffffff)
 413             continue;
 414         u32 s = en->start, e = end;
 415         if (!highram) {
 416             u32 newe = ALIGN_DOWN(e - BUILD_MAX_HIGHTABLE, MALLOC_MIN_ALIGN);
 417             if (newe <= e && newe >= s) {
 418                 highram = newe;
 419                 e = newe;
 420             }
 421         }
 422         addSpace(&ZoneTmpHigh, (void*)s, (void*)e);
 423     }
 424
 425     // Populate regions
 426     addSpace(&ZoneTmpLow, (void*)BUILD_STACK_ADDR, (void*)BUILD_EBDA_MINIMUM);
 427     if (highram) {
 428         addSpace(&ZoneHigh, (void*)highram
 429                  , (void*)highram + BUILD_MAX_HIGHTABLE);
 430         add_e820(highram, BUILD_MAX_HIGHTABLE, E820_RESERVED);
 431     }
 432 }
 433
 434 void
 435 csm_malloc_preinit(u32 low_pmm, u32 low_pmm_size, u32 hi_pmm, u32 hi_pmm_size)
 436 {
 437     ASSERT32FLAT();
 438
 439     if (hi_pmm_size > BUILD_MAX_HIGHTABLE) {
 440         void *hi_pmm_end = (void *)hi_pmm + hi_pmm_size;
 441         addSpace(&ZoneTmpHigh, (void *)hi_pmm, hi_pmm_end - BUILD_MAX_HIGHTABLE);
 442         addSpace(&ZoneHigh, hi_pmm_end - BUILD_MAX_HIGHTABLE, hi_pmm_end);
 443     } else {
 444         addSpace(&ZoneTmpHigh, (void *)hi_pmm, (void *)hi_pmm + hi_pmm_size);
 445     }
 446     addSpace(&ZoneTmpLow, (void *)low_pmm, (void *)low_pmm + low_pmm_size);
 447 }
 448
 449 u32 LegacyRamSize VARFSEG;
 450
 451 // Calculate the maximum ramsize (less than 4gig) from e820 map.
 452 static void
 453 calcRamSize(void)
 454 {
 455     u32 rs = 0;
 456     int i;
 457     for (i=e820_count-1; i>=0; i--) {
 458         struct e820entry *en = &e820_list[i];
 459         u64 end = en->start + en->size;
 460         u32 type = en->type;
 461         if (end <= 0xffffffff && (type == E820_ACPI || type == E820_RAM)) {
 462             rs = end;
 463             break;
 464         }
 465     }
 466     LegacyRamSize = rs >= 1024*1024 ? rs : 1024*1024;
 467 }
 468
 469 // Update pointers after code relocation.
 470 void
 471 malloc_init(void)
 472 {
 473     ASSERT32FLAT();
 474     dprintf(3, "malloc init\n");
 475
 476     if (CONFIG_RELOCATE_INIT) {
 477         // Fixup malloc pointers after relocation
 478         int i;
 479         for (i=0; i<ARRAY_SIZE(Zones); i++) {
 480             struct zone_s *zone = Zones[i];
 481             if (zone->head.first)
 482                 zone->head.first->pprev = &zone->head.first;
 483         }
 484     }
 485
 486     // Initialize low-memory region
 487     extern u8 varlow_start[], varlow_end[], final_varlow_start[];
 488     memmove(final_varlow_start, varlow_start, varlow_end - varlow_start);
 489     if (CONFIG_MALLOC_UPPERMEMORY) {
 490         addSpace(&ZoneLow, zonelow_base + OPROM_HEADER_RESERVE
 491                  , final_varlow_start);
 492         RomBase = findLast(&ZoneLow);
 493     } else {
 494         addSpace(&ZoneLow, (void*)ALIGN_DOWN((u32)final_varlow_start, 1024)
 495                  , final_varlow_start);
 496     }
 497
 498     // Add space available in f-segment to ZoneFSeg
 499     extern u8 zonefseg_start[], zonefseg_end[];
 500     memset(zonefseg_start, 0, zonefseg_end - zonefseg_start);
 501     addSpace(&ZoneFSeg, zonefseg_start, zonefseg_end);
 502
 503     calcRamSize();
 504 }
 505
 506 void
 507 malloc_prepboot(void)
 508 {
 509     ASSERT32FLAT();
 510     dprintf(3, "malloc finalize\n");
 511
 512     u32 base = rom_get_max();
 513     memset((void*)RomEnd, 0, base-RomEnd);
 514     if (CONFIG_MALLOC_UPPERMEMORY) {
 515         // Place an optionrom signature around used low mem area.
 516         struct rom_header *dummyrom = (void*)base;
 517         dummyrom->signature = OPTION_ROM_SIGNATURE;
 518         int size = (BUILD_BIOS_ADDR - base) / 512;
 519         dummyrom->size = (size > 255) ? 255 : size;
 520     }
 521
 522     // Reserve more low-mem if needed.
 523     u32 endlow = GET_BDA(mem_size_kb)*1024;
 524     add_e820(endlow, BUILD_LOWRAM_END-endlow, E820_RESERVED);
 525
 526     // Clear unused f-seg ram.
 527     struct allocinfo_s *info = findLast(&ZoneFSeg);
 528     memset(info->dataend, 0, info->allocend - info->dataend);
 529     dprintf(1, "Space available for UMB: %x-%x, %x-%x\n"
 530             , RomEnd, base, (u32)info->dataend, (u32)info->allocend);
 531
 532     // Give back unused high ram.
 533     info = findLast(&ZoneHigh);
 534     if (info) {
 535         u32 giveback = ALIGN_DOWN(info->allocend - info->dataend, PAGE_SIZE);
 536         add_e820((u32)info->dataend, giveback, E820_RAM);
 537         dprintf(1, "Returned %d bytes of ZoneHigh\n", giveback);
 538     }
 539
 540     calcRamSize();
 541 }