1 /*
2 * COPYRIGHT: GPLv2+ - See COPYING in the top level directory
3 * PROJECT: ReactOS Virtual DOS Machine
4 * FILE: subsystems/mvdm/ntvdm/bios/umamgr.c
5 * PURPOSE: Upper Memory Area Manager
6 * PROGRAMMERS: Hermes Belusca-Maito (hermes.belusca@sfr.fr)
7 *
8 * NOTE: The UMA Manager is used by the DOS XMS Driver (UMB Provider part),
9 * indirectly by the DOS EMS Driver, and by VDD memory management functions.
10 */
11
12 /* INCLUDES *******************************************************************/
13
14 #include "ntvdm.h"
15
16 #define NDEBUG
17 #include <debug.h>
18
19 #include "emulator.h"
20 #include "memory.h"
21
22 #include "umamgr.h"
23
24 /* PRIVATE VARIABLES **********************************************************/
25
26 typedef struct _UMA_DESCRIPTOR
27 {
28 LIST_ENTRY Entry;
29 ULONG Start;
30 ULONG Size;
31 UMA_DESC_TYPE Type;
32 } UMA_DESCRIPTOR, *PUMA_DESCRIPTOR;
33
34 /*
35 * Sorted list of UMA descriptors.
36 *
37 * The descriptor list is (and must always be) sorted by memory addresses,
38 * and all consecutive free descriptors are always merged together, so that
39 * free ones are always separated from each other by descriptors of other types.
40 *
41 * TODO: Add the fact that no blocks of size == 0 are allowed.
42 */
43 static LIST_ENTRY UmaDescriptorList = { &UmaDescriptorList, &UmaDescriptorList };
44
45 /* PRIVATE FUNCTIONS **********************************************************/
46
47 static PUMA_DESCRIPTOR
CreateUmaDescriptor(IN OUT PLIST_ENTRY ListHead,IN ULONG Address,IN ULONG Size,IN UMA_DESC_TYPE Type)48 CreateUmaDescriptor(IN OUT PLIST_ENTRY ListHead,
49 IN ULONG Address,
50 IN ULONG Size,
51 IN UMA_DESC_TYPE Type)
52 {
53 PUMA_DESCRIPTOR UmaDesc;
54
55 ASSERT(Size > 0);
56
57 UmaDesc = RtlAllocateHeap(RtlGetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(*UmaDesc));
58 if (!UmaDesc) return NULL;
59
60 UmaDesc->Start = Address;
61 UmaDesc->Size = Size;
62 UmaDesc->Type = Type;
63
64 /*
65 * We use the trick of http://www.osronline.com/article.cfm?article=499 to insert
66 * the new descriptor just after the current entry that we specify via 'ListHead'.
67 * If 'ListHead' is NULL then we insert the descriptor at the tail of 'UmaDescriptorList'
68 * (which is equivalent to inserting it at the head of 'UmaDescriptorList.Blink').
69 */
70 if (ListHead == NULL) ListHead = UmaDescriptorList.Blink;
71 InsertHeadList(ListHead, &UmaDesc->Entry);
72
73 return UmaDesc;
74 }
75
FreeUmaDescriptor(PUMA_DESCRIPTOR UmaDesc)76 static VOID FreeUmaDescriptor(PUMA_DESCRIPTOR UmaDesc)
77 {
78 RemoveEntryList(&UmaDesc->Entry);
79 RtlFreeHeap(RtlGetProcessHeap(), 0, UmaDesc);
80 }
81
82 /* PUBLIC FUNCTIONS ***********************************************************/
83
UmaDescReserve(IN OUT PUSHORT Segment,IN OUT PUSHORT Size)84 BOOLEAN UmaDescReserve(IN OUT PUSHORT Segment, IN OUT PUSHORT Size)
85 {
86 ULONG Address = (*Segment << 4); // Convert segment number into address.
87 ULONG RequestSize = (*Size << 4); // Convert size in paragraphs into size in bytes.
88 ULONG MaxSize = 0;
89 PLIST_ENTRY Entry;
90 PUMA_DESCRIPTOR UmaDesc, NewUmaDesc;
91 PUMA_DESCRIPTOR FoundUmaDesc = NULL;
92
93 // FIXME: Check! What to do?
94 if (RequestSize == 0) DPRINT1("Requesting UMA descriptor with null size?!\n");
95
96 Entry = UmaDescriptorList.Flink;
97 while (Entry != &UmaDescriptorList)
98 {
99 UmaDesc = (PUMA_DESCRIPTOR)CONTAINING_RECORD(Entry, UMA_DESCRIPTOR, Entry);
100 Entry = Entry->Flink;
101
102 /* Only check free descriptors */
103 if (UmaDesc->Type != UMA_FREE) continue;
104
105 /* Update the maximum descriptor size */
106 if (UmaDesc->Size > MaxSize) MaxSize = UmaDesc->Size;
107
108 /* Descriptor too small, continue... */
109 if (UmaDesc->Size < RequestSize) continue;
110
111 /* Do we want to reserve the descriptor at a precise address? */
112 if (Address)
113 {
114 /* If the descriptor ends before the desired region, try again */
115 if (UmaDesc->Start + UmaDesc->Size <= Address) continue;
116
117 /*
118 * If we have a descriptor, but one of its boundaries crosses the
119 * desired region (it starts after the desired region, or ends
120 * before the end of the desired region), this means that there
121 * is already something inside the region, so that we cannot
122 * allocate the region here. Bail out.
123 */
124 if (UmaDesc->Start > Address ||
125 UmaDesc->Start + UmaDesc->Size < Address + RequestSize)
126 {
127 goto Fail;
128 }
129
130 /* We now have a free descriptor that overlaps our desired region: split it */
131
132 /*
133 * Here, UmaDesc->Start == Address or UmaDesc->Start < Address,
134 * in which case we need to split the descriptor to the left.
135 */
136 if (UmaDesc->Start < Address)
137 {
138 /* Create a new free descriptor and insert it after the current one */
139 NewUmaDesc = CreateUmaDescriptor(&UmaDesc->Entry,
140 Address,
141 UmaDesc->Size - (Address - UmaDesc->Start),
142 UmaDesc->Type); // UMA_FREE
143 if (!NewUmaDesc)
144 {
145 DPRINT1("CreateUmaDescriptor failed, UMA descriptor list possibly corrupted!\n");
146 goto Fail;
147 }
148
149 /* Reduce the size of the splitted left descriptor */
150 UmaDesc->Size = (Address - UmaDesc->Start);
151
152 /* Current descriptor is now the new created one */
153 UmaDesc = NewUmaDesc;
154 }
155
156 /* Here, UmaDesc->Start == Address */
157 }
158
159 /* Descriptor of large enough size: split it to the right if needed */
160 // FIXME: It might be needed to consider a minimum size starting which we need to split.
161 // if (UmaDesc->Size - RequestSize > (3 << 4))
162 if (UmaDesc->Size > RequestSize)
163 {
164 /*
165 * Create a new free descriptor and insert it after the current one.
166 * Because consecutive free descriptors are always merged together,
167 * the descriptor following 'UmaDesc' cannot be free, so that this
168 * new free descriptor does not need to be merged with some others.
169 */
170 NewUmaDesc = CreateUmaDescriptor(&UmaDesc->Entry,
171 UmaDesc->Start + RequestSize,
172 UmaDesc->Size - RequestSize,
173 UmaDesc->Type); // UMA_FREE
174 if (!NewUmaDesc)
175 {
176 DPRINT1("CreateUmaDescriptor failed, UMA descriptor list possibly corrupted!\n");
177 goto Fail;
178 }
179
180 /* Reduce the size of the splitted left descriptor */
181 UmaDesc->Size = RequestSize;
182 }
183
184 /* We have a descriptor of correct size, initialize it */
185 UmaDesc->Type = UMA_UMB;
186 FoundUmaDesc = UmaDesc;
187 break;
188 }
189
190 if (FoundUmaDesc)
191 {
192 /* Returned address is a segment and size is in paragraphs */
193 *Segment = (FoundUmaDesc->Start >> 4);
194 *Size = (FoundUmaDesc->Size >> 4);
195 return TRUE;
196 }
197 else
198 {
199 Fail:
200 /* Returned address is a segment and size is in paragraphs */
201 *Segment = 0x0000;
202 *Size = (MaxSize >> 4);
203 return FALSE;
204 }
205 }
206
UmaDescRelease(IN USHORT Segment)207 BOOLEAN UmaDescRelease(IN USHORT Segment)
208 {
209 ULONG Address = (Segment << 4); // Convert segment number into address.
210 PLIST_ENTRY Entry, PrevEntry, NextEntry;
211 PUMA_DESCRIPTOR UmaDesc, PrevDesc = NULL, NextDesc = NULL;
212 PUMA_DESCRIPTOR FoundUmaDesc = NULL;
213
214 Entry = UmaDescriptorList.Flink;
215 while (Entry != &UmaDescriptorList)
216 {
217 UmaDesc = (PUMA_DESCRIPTOR)CONTAINING_RECORD(Entry, UMA_DESCRIPTOR, Entry);
218 Entry = Entry->Flink;
219
220 /* Search for the descriptor in the list */
221 if (UmaDesc->Start == Address && UmaDesc->Type == UMA_UMB)
222 {
223 /* We found it */
224 FoundUmaDesc = UmaDesc;
225 break;
226 }
227 }
228
229 if (FoundUmaDesc)
230 {
231 FoundUmaDesc->Type = UMA_FREE;
232
233 /* Combine free descriptors adjacent to this one */
234 PrevEntry = FoundUmaDesc->Entry.Blink;
235 NextEntry = FoundUmaDesc->Entry.Flink;
236
237 if (PrevEntry != &UmaDescriptorList)
238 PrevDesc = (PUMA_DESCRIPTOR)CONTAINING_RECORD(PrevEntry, UMA_DESCRIPTOR, Entry);
239 if (NextEntry != &UmaDescriptorList)
240 NextDesc = (PUMA_DESCRIPTOR)CONTAINING_RECORD(NextEntry, UMA_DESCRIPTOR, Entry);
241
242 if (NextDesc && NextDesc->Type == FoundUmaDesc->Type) // UMA_FREE
243 {
244 FoundUmaDesc->Size += NextDesc->Size;
245 FreeUmaDescriptor(NextDesc);
246 }
247
248 if (PrevDesc && PrevDesc->Type == FoundUmaDesc->Type) // UMA_FREE
249 {
250 PrevDesc->Size += FoundUmaDesc->Size;
251 FreeUmaDescriptor(FoundUmaDesc);
252 }
253
254 return TRUE;
255 }
256
257 return FALSE;
258 }
259
UmaDescReallocate(IN USHORT Segment,IN OUT PUSHORT Size)260 BOOLEAN UmaDescReallocate(IN USHORT Segment, IN OUT PUSHORT Size)
261 {
262 ULONG Address = (Segment << 4); // Convert segment number into address.
263 ULONG RequestSize = (*Size << 4); // Convert size in paragraphs into size in bytes.
264 ULONG MaxSize = 0;
265 PLIST_ENTRY Entry, NextEntry;
266 PUMA_DESCRIPTOR UmaDesc, NextDesc = NULL, NewUmaDesc;
267 PUMA_DESCRIPTOR FoundUmaDesc = NULL;
268
269 // FIXME: Check! What to do?
270 if (RequestSize == 0) DPRINT1("Resizing UMA descriptor %04X to null size?!\n", Segment);
271
272 Entry = UmaDescriptorList.Flink;
273 while (Entry != &UmaDescriptorList)
274 {
275 UmaDesc = (PUMA_DESCRIPTOR)CONTAINING_RECORD(Entry, UMA_DESCRIPTOR, Entry);
276 Entry = Entry->Flink;
277
278 /* Only get the maximum size of free descriptors */
279 if (UmaDesc->Type == UMA_FREE)
280 {
281 /* Update the maximum descriptor size */
282 if (UmaDesc->Size > MaxSize) MaxSize = UmaDesc->Size;
283 }
284
285 /* Search for the descriptor in the list */
286 if (UmaDesc->Start == Address && UmaDesc->Type == UMA_UMB)
287 {
288 /* We found it */
289 FoundUmaDesc = UmaDesc;
290 break;
291 }
292 }
293
294 if (FoundUmaDesc)
295 {
296 /* If we do not resize anything, just quit with success */
297 if (FoundUmaDesc->Size == RequestSize) goto Success;
298
299 NextEntry = FoundUmaDesc->Entry.Flink;
300
301 if (NextEntry != &UmaDescriptorList)
302 NextDesc = (PUMA_DESCRIPTOR)CONTAINING_RECORD(NextEntry, UMA_DESCRIPTOR, Entry);
303
304 /* Check for reduction or enlargement */
305 if (FoundUmaDesc->Size > RequestSize)
306 {
307 /* Reduction */
308
309 /*
310 * Check if the next descriptor is free, in which case we
311 * extend it, otherwise we create a new free descriptor.
312 */
313 if (NextDesc && NextDesc->Type == UMA_FREE)
314 {
315 /* Yes it is, expand its size and move it down */
316 NextDesc->Size += (FoundUmaDesc->Size - RequestSize);
317 NextDesc->Start -= (FoundUmaDesc->Size - RequestSize);
318 }
319 else
320 {
321 // FIXME: It might be needed to consider a minimum size starting which we need to split.
322 // if (FoundUmaDesc->Size - RequestSize > (3 << 4))
323
324 /* Create a new free descriptor and insert it after the current one */
325 NewUmaDesc = CreateUmaDescriptor(&FoundUmaDesc->Entry,
326 FoundUmaDesc->Start + RequestSize,
327 FoundUmaDesc->Size - RequestSize,
328 FoundUmaDesc->Type);
329 if (!NewUmaDesc)
330 {
331 DPRINT1("CreateUmaDescriptor failed, UMA descriptor list possibly corrupted!\n");
332 MaxSize = 0;
333 goto Fail;
334 }
335 }
336 }
337 else // if (FoundUmaDesc->Size <= RequestSize)
338 {
339 /* Enlargement */
340
341 /* Check whether the next descriptor is free and large enough for merging */
342 if (NextDesc && NextDesc->Type == UMA_FREE &&
343 FoundUmaDesc->Size + NextDesc->Size >= RequestSize)
344 {
345 /* Yes it is, reduce its size and move it up, and enlarge the reallocated descriptor */
346 NextDesc->Size -= (RequestSize - FoundUmaDesc->Size);
347 NextDesc->Start += (RequestSize - FoundUmaDesc->Size);
348
349 if (NextDesc->Size == 0) FreeUmaDescriptor(NextDesc);
350 }
351 else
352 {
353 MaxSize = 0;
354 goto Fail;
355 }
356 }
357
358 /* Finally, resize the descriptor */
359 FoundUmaDesc->Size = RequestSize;
360
361 Success:
362 /* Returned size is in paragraphs */
363 *Size = (FoundUmaDesc->Size >> 4);
364 return TRUE;
365 }
366 else
367 {
368 Fail:
369 /* Returned size is in paragraphs */
370 *Size = (MaxSize >> 4);
371 return FALSE;
372 }
373 }
374
UmaMgrInitialize(VOID)375 BOOLEAN UmaMgrInitialize(VOID)
376 {
377 // See bios/rom.h
378 #define ROM_AREA_START 0xE0000
379 #define ROM_AREA_END 0xFFFFF
380
381 #define OPTION_ROM_SIGNATURE 0xAA55
382
383 PUMA_DESCRIPTOR UmaDesc = NULL;
384 ULONG StartAddress = 0;
385 ULONG Size = 0;
386 UMA_DESC_TYPE Type = UMA_FREE;
387
388 UINT i;
389
390 ULONG Start, End;
391 ULONG Increment;
392
393 ULONG Address;
394
395 // ULONG RomStart[] = {};
396 // ULONG RomEnd[] = {};
397 ULONG RomBoundaries[] = {0xA0000, 0xC0000, /*0xC8000, 0xE0000,*/ 0xF0000, 0x100000};
398 ULONG SizeIncrement[] = {0x20000, 0x00800, /*0x00800, 0x10000,*/ 0x10000, 0x0000 };
399
400 // InitializeListHead(&UmaDescriptorList);
401
402 /* NOTE: There must be always one UMA descriptor at least */
403 // FIXME: Maybe it should be a static object?
404
405 for (i = 0; i < ARRAYSIZE(RomBoundaries) - 1; i++)
406 {
407 Start = RomBoundaries[i]; // RomStart[i]
408 End = RomBoundaries[i+1]; // RomEnd[i]
409 Increment = SizeIncrement[i];
410
411 for (Address = Start; Address < End; Address += Increment)
412 {
413 if (StartAddress == 0)
414 {
415 /* Initialize data for a new descriptor */
416 StartAddress = Address;
417 Size = 0;
418 Type = UMA_FREE;
419 }
420
421 /* Is it a normal system zone/user-excluded zone? */
422 if (Address >= 0xA0000 && Address < 0xC0000)
423 {
424 // StartAddress = Address;
425 Size = Increment;
426 Type = UMA_SYSTEM;
427
428 /* Create descriptor */
429 UmaDesc = CreateUmaDescriptor(NULL, StartAddress, Size, Type);
430 if (!UmaDesc) return FALSE;
431
432 StartAddress = 0;
433 continue;
434 }
435 /* Is it the PC ROM BIOS? */
436 else if (Address >= 0xF0000)
437 {
438 // StartAddress = Address;
439 Size = 0x10000; // Increment;
440 Type = UMA_ROM;
441
442 /* Create descriptor */
443 UmaDesc = CreateUmaDescriptor(NULL, StartAddress, Size, Type);
444 if (!UmaDesc) return FALSE;
445
446 StartAddress = 0;
447 continue;
448 }
449 /* Is it an option ROM? */
450 else if (Address >= 0xC0000 && Address < 0xF0000)
451 {
452 ULONG RomSize;
453 ULONG PrevRomAddress = 0;
454 ULONG PrevRomSize = 0;
455
456 // while (Address < 0xF0000)
457 for (; Address < 0xF0000; Address += Increment)
458 {
459
460 #if 0 // FIXME: Is this block, better here...
461 {
462 // We may be looping inside a ROM block, if: Type == 2 and:
463 // (StartAddress <= Address &&) StartAddress + Size > Address.
464 // In this case, do nothing (do not increase size either)
465 // But if we are now outside of a ROM block, then we need
466 // to create the previous block, and initialize a new empty one!
467 // (and following the next passages, increase its size).
468
469 // if (StartAddress < Address && Type != 2)
470 if (Type == UMA_ROM && StartAddress + Size > Address)
471 {
472 /* We are inside ROM, do nothing */
473 }
474 else if (Type == UMA_ROM && StartAddress + Size <= Address)
475 {
476 /* We finished a ROM descriptor */
477
478 /* Create descriptor */
479 UmaDesc = CreateUmaDescriptor(NULL, StartAddress, Size, Type);
480 if (!UmaDesc) return FALSE;
481
482 StartAddress = 0;
483 // goto Restart;
484 }
485 else if (Type != UMA_ROM)
486 {
487 Size += Increment;
488 }
489 }
490 #endif
491
492 Restart:
493 /// if (Address >= 0xE0000) { Increment = 0x10000; }
494
495 if (StartAddress == 0)
496 {
497 /* Initialize data for a new descriptor */
498 StartAddress = Address;
499 Size = 0;
500 Type = UMA_FREE;
501
502 PrevRomAddress = 0;
503 PrevRomSize = 0;
504 }
505
506 if (*(PUSHORT)REAL_TO_PHYS(Address) == OPTION_ROM_SIGNATURE)
507 {
508 /*
509 * If this is an adapter ROM (Start: C8000, End: E0000),
510 * its reported size is stored in byte 2 of the ROM.
511 *
512 * If this is an expansion ROM (Start: E0000, End: F0000),
513 * its real length is 64kB.
514 */
515 RomSize = *(PUCHAR)REAL_TO_PHYS(Address + 2) * 512;
516 // if (Address >= 0xE0000) RomSize = 0x10000;
517 if (Address >= 0xE0000) { RomSize = 0x10000; Increment = RomSize; }
518
519 DPRINT1("ROM present @ address 0x%p\n", Address);
520
521 if (StartAddress != 0 && Size != 0 &&
522 StartAddress + Size <= Address)
523 {
524 /* Finish old descriptor */
525 UmaDesc = CreateUmaDescriptor(NULL, StartAddress, Size, Type);
526 if (!UmaDesc) return FALSE;
527 }
528
529 /*
530 * We may have overlapping ROMs, when PrevRomAddress + PrevRomSize > RomAddress.
531 * They must be put inside the same UMA descriptor.
532 */
533 if (PrevRomAddress + PrevRomSize > /*Rom*/Address)
534 {
535 // Overlapping ROM
536
537 /*
538 * PrevRomAddress remains the same, but adjust
539 * PrevRomSize (ROM descriptors merging).
540 */
541 PrevRomSize = max(PrevRomSize, RomSize + Address - PrevRomAddress);
542
543 // FIX: Confirm that the start address is really
544 // the one of the previous descriptor.
545 StartAddress = PrevRomAddress;
546 Size = PrevRomSize;
547 Type = UMA_ROM;
548 }
549 else
550 {
551 // Non-overlapping ROM
552
553 PrevRomAddress = Address;
554 PrevRomSize = RomSize;
555
556 /* Initialize a new descriptor. We will create it when it's OK */
557 StartAddress = Address;
558 Size = RomSize;
559 Type = UMA_ROM;
560 // continue;
561 }
562 }
563 #if 1 // FIXME: ...or there??
564 else
565 {
566 // We may be looping inside a ROM block, if: Type == 2 and:
567 // (StartAddress <= Address &&) StartAddress + Size > Address.
568 // In this case, do nothing (do not increase size either)
569 // But if we are now outside of a ROM block, then we need
570 // to create the previous block, and initialize a new empty one!
571 // (and following the next passages, increase its size).
572
573 // if (StartAddress < Address && Type != UMA_ROM)
574 if (Type == UMA_ROM && StartAddress + Size > Address)
575 {
576 // We are inside ROM, do nothing
577 }
578 else if (Type == UMA_ROM && StartAddress + Size <= Address)
579 {
580 // We finished a ROM descriptor.
581
582 /* Create descriptor */
583 UmaDesc = CreateUmaDescriptor(NULL, StartAddress, Size, Type);
584 if (!UmaDesc) return FALSE;
585
586 StartAddress = 0;
587 goto Restart;
588 }
589 else if (Type != UMA_ROM)
590 {
591 Size += Increment;
592 }
593 }
594 #endif
595
596 // Fixed incroment; we may encounter again overlapping ROMs, etc.
597 // Address += Increment;
598 }
599
600 if (StartAddress != 0 && Size != 0)
601 {
602 /* Create descriptor */
603 UmaDesc = CreateUmaDescriptor(NULL, StartAddress, Size, Type);
604 if (!UmaDesc) return FALSE;
605
606 StartAddress = 0;
607 }
608
609 }
610 }
611 }
612
613 return TRUE;
614 }
615
UmaMgrCleanup(VOID)616 VOID UmaMgrCleanup(VOID)
617 {
618 PUMA_DESCRIPTOR UmaDesc;
619
620 while (!IsListEmpty(&UmaDescriptorList))
621 {
622 UmaDesc = (PUMA_DESCRIPTOR)CONTAINING_RECORD(UmaDescriptorList.Flink, UMA_DESCRIPTOR, Entry);
623 FreeUmaDescriptor(UmaDesc);
624 }
625 }
626
627 /* EOF */
628