2 * COPYRIGHT: GPLv2+ - See COPYING in the top level directory
3 * PROJECT: ReactOS Virtual DOS Machine
5 * PURPOSE: Upper Memory Area Manager
6 * PROGRAMMERS: Hermes Belusca-Maito (hermes.belusca@sfr.fr)
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.
12 /* INCLUDES *******************************************************************/
22 /* PRIVATE VARIABLES **********************************************************/
24 typedef struct _UMA_DESCRIPTOR
30 } UMA_DESCRIPTOR
, *PUMA_DESCRIPTOR
;
33 * Sorted list of UMA descriptors.
35 * The descriptor list is (and must always be) sorted by memory addresses,
36 * and all consecutive free descriptors are always merged together, so that
37 * free ones are always separated from each other by descriptors of other types.
39 * TODO: Add the fact that no blocks of size == 0 are allowed.
41 static LIST_ENTRY UmaDescriptorList
= { &UmaDescriptorList
, &UmaDescriptorList
};
43 /* PRIVATE FUNCTIONS **********************************************************/
45 static PUMA_DESCRIPTOR
46 CreateUmaDescriptor(IN OUT PLIST_ENTRY ListHead
,
49 IN UMA_DESC_TYPE Type
)
51 PUMA_DESCRIPTOR UmaDesc
;
55 UmaDesc
= RtlAllocateHeap(RtlGetProcessHeap(), HEAP_ZERO_MEMORY
, sizeof(*UmaDesc
));
56 if (!UmaDesc
) return NULL
;
58 UmaDesc
->Start
= Address
;
63 * We use the trick of http://www.osronline.com/article.cfm?article=499 to insert
64 * the new descriptor just after the current entry that we specify via 'ListHead'.
65 * If 'ListHead' is NULL then we insert the descriptor at the tail of 'UmaDescriptorList'
66 * (which is equivalent to inserting it at the head of 'UmaDescriptorList.Blink').
68 if (ListHead
== NULL
) ListHead
= UmaDescriptorList
.Blink
;
69 InsertHeadList(ListHead
, &UmaDesc
->Entry
);
74 static VOID
FreeUmaDescriptor(PUMA_DESCRIPTOR UmaDesc
)
76 RemoveEntryList(&UmaDesc
->Entry
);
77 RtlFreeHeap(RtlGetProcessHeap(), 0, UmaDesc
);
80 /* PUBLIC FUNCTIONS ***********************************************************/
82 BOOLEAN
UmaDescReserve(IN OUT PUSHORT Segment
, IN OUT PUSHORT Size
)
84 ULONG Address
= (*Segment
<< 4); // Convert segment number into address.
85 ULONG RequestSize
= (*Size
<< 4); // Convert size in paragraphs into size in bytes.
88 PUMA_DESCRIPTOR UmaDesc
, NewUmaDesc
;
89 PUMA_DESCRIPTOR FoundUmaDesc
= NULL
;
91 // FIXME: Check! What to do?
92 if (RequestSize
== 0) DPRINT1("Requesting UMA descriptor with null size?!\n");
94 Entry
= UmaDescriptorList
.Flink
;
95 while (Entry
!= &UmaDescriptorList
)
97 UmaDesc
= (PUMA_DESCRIPTOR
)CONTAINING_RECORD(Entry
, UMA_DESCRIPTOR
, Entry
);
100 /* Only check free descriptors */
101 if (UmaDesc
->Type
!= UMA_FREE
) continue;
103 /* Update the maximum descriptor size */
104 if (UmaDesc
->Size
> MaxSize
) MaxSize
= UmaDesc
->Size
;
106 /* Descriptor too small, continue... */
107 if (UmaDesc
->Size
< RequestSize
) continue;
109 /* Do we want to reserve the descriptor at a precise address? */
112 /* If the descriptor ends before the desired region, try again */
113 if (UmaDesc
->Start
+ UmaDesc
->Size
<= Address
) continue;
116 * If we have a descriptor, but one of its boundaries crosses the
117 * desired region (it starts after the desired region, or ends
118 * before the end of the desired region), this means that there
119 * is already something inside the region, so that we cannot
120 * allocate the region here. Bail out.
122 if (UmaDesc
->Start
> Address
||
123 UmaDesc
->Start
+ UmaDesc
->Size
< Address
+ RequestSize
)
128 /* We now have a free descriptor that overlaps our desired region: split it */
131 * Here, UmaDesc->Start == Address or UmaDesc->Start < Address,
132 * in which case we need to split the descriptor to the left.
134 if (UmaDesc
->Start
< Address
)
136 /* Create a new free descriptor and insert it after the current one */
137 NewUmaDesc
= CreateUmaDescriptor(&UmaDesc
->Entry
,
139 UmaDesc
->Size
- (Address
- UmaDesc
->Start
),
140 UmaDesc
->Type
); // UMA_FREE
143 DPRINT1("CreateUmaDescriptor failed, UMA descriptor list possibly corrupted!\n");
147 /* Reduce the size of the splitted left descriptor */
148 UmaDesc
->Size
= (Address
- UmaDesc
->Start
);
150 /* Current descriptor is now the new created one */
151 UmaDesc
= NewUmaDesc
;
154 /* Here, UmaDesc->Start == Address */
157 /* Descriptor of large enough size: split it to the right if needed */
158 // FIXME: It might be needed to consider a minimum size starting which we need to split.
159 // if (UmaDesc->Size - RequestSize > (3 << 4))
160 if (UmaDesc
->Size
> RequestSize
)
163 * Create a new free descriptor and insert it after the current one.
164 * Because consecutive free descriptors are always merged together,
165 * the descriptor following 'UmaDesc' cannot be free, so that this
166 * new free descriptor does not need to be merged with some others.
168 NewUmaDesc
= CreateUmaDescriptor(&UmaDesc
->Entry
,
169 UmaDesc
->Start
+ RequestSize
,
170 UmaDesc
->Size
- RequestSize
,
171 UmaDesc
->Type
); // UMA_FREE
174 DPRINT1("CreateUmaDescriptor failed, UMA descriptor list possibly corrupted!\n");
178 /* Reduce the size of the splitted left descriptor */
179 UmaDesc
->Size
= RequestSize
;
182 /* We have a descriptor of correct size, initialize it */
183 UmaDesc
->Type
= UMA_UMB
;
184 FoundUmaDesc
= UmaDesc
;
190 /* Returned address is a segment and size is in paragraphs */
191 *Segment
= (FoundUmaDesc
->Start
>> 4);
192 *Size
= (FoundUmaDesc
->Size
>> 4);
198 /* Returned address is a segment and size is in paragraphs */
200 *Size
= (MaxSize
>> 4);
205 BOOLEAN
UmaDescRelease(IN USHORT Segment
)
207 ULONG Address
= (Segment
<< 4); // Convert segment number into address.
208 PLIST_ENTRY Entry
, PrevEntry
, NextEntry
;
209 PUMA_DESCRIPTOR UmaDesc
, PrevDesc
= NULL
, NextDesc
= NULL
;
210 PUMA_DESCRIPTOR FoundUmaDesc
= NULL
;
212 Entry
= UmaDescriptorList
.Flink
;
213 while (Entry
!= &UmaDescriptorList
)
215 UmaDesc
= (PUMA_DESCRIPTOR
)CONTAINING_RECORD(Entry
, UMA_DESCRIPTOR
, Entry
);
216 Entry
= Entry
->Flink
;
218 /* Search for the descriptor in the list */
219 if (UmaDesc
->Start
== Address
&& UmaDesc
->Type
== UMA_UMB
)
222 FoundUmaDesc
= UmaDesc
;
229 FoundUmaDesc
->Type
= UMA_FREE
;
231 /* Combine free descriptors adjacent to this one */
232 PrevEntry
= FoundUmaDesc
->Entry
.Blink
;
233 NextEntry
= FoundUmaDesc
->Entry
.Flink
;
235 if (PrevEntry
!= &UmaDescriptorList
)
236 PrevDesc
= (PUMA_DESCRIPTOR
)CONTAINING_RECORD(PrevEntry
, UMA_DESCRIPTOR
, Entry
);
237 if (NextEntry
!= &UmaDescriptorList
)
238 NextDesc
= (PUMA_DESCRIPTOR
)CONTAINING_RECORD(NextEntry
, UMA_DESCRIPTOR
, Entry
);
240 if (NextDesc
&& NextDesc
->Type
== FoundUmaDesc
->Type
) // UMA_FREE
242 FoundUmaDesc
->Size
+= NextDesc
->Size
;
243 FreeUmaDescriptor(NextDesc
);
246 if (PrevDesc
&& PrevDesc
->Type
== FoundUmaDesc
->Type
) // UMA_FREE
248 PrevDesc
->Size
+= FoundUmaDesc
->Size
;
249 FreeUmaDescriptor(FoundUmaDesc
);
258 BOOLEAN
UmaDescReallocate(IN USHORT Segment
, IN OUT PUSHORT Size
)
260 ULONG Address
= (Segment
<< 4); // Convert segment number into address.
261 ULONG RequestSize
= (*Size
<< 4); // Convert size in paragraphs into size in bytes.
263 PLIST_ENTRY Entry
, NextEntry
;
264 PUMA_DESCRIPTOR UmaDesc
, NextDesc
= NULL
, NewUmaDesc
;
265 PUMA_DESCRIPTOR FoundUmaDesc
= NULL
;
267 // FIXME: Check! What to do?
268 if (RequestSize
== 0) DPRINT1("Resizing UMA descriptor %04X to null size?!\n", Segment
);
270 Entry
= UmaDescriptorList
.Flink
;
271 while (Entry
!= &UmaDescriptorList
)
273 UmaDesc
= (PUMA_DESCRIPTOR
)CONTAINING_RECORD(Entry
, UMA_DESCRIPTOR
, Entry
);
274 Entry
= Entry
->Flink
;
276 /* Only get the maximum size of free descriptors */
277 if (UmaDesc
->Type
== UMA_FREE
)
279 /* Update the maximum descriptor size */
280 if (UmaDesc
->Size
> MaxSize
) MaxSize
= UmaDesc
->Size
;
283 /* Search for the descriptor in the list */
284 if (UmaDesc
->Start
== Address
&& UmaDesc
->Type
== UMA_UMB
)
287 FoundUmaDesc
= UmaDesc
;
294 /* If we do not resize anything, just quit with success */
295 if (FoundUmaDesc
->Size
== RequestSize
) goto Success
;
297 NextEntry
= FoundUmaDesc
->Entry
.Flink
;
299 if (NextEntry
!= &UmaDescriptorList
)
300 NextDesc
= (PUMA_DESCRIPTOR
)CONTAINING_RECORD(NextEntry
, UMA_DESCRIPTOR
, Entry
);
302 /* Check for reduction or enlargement */
303 if (FoundUmaDesc
->Size
> RequestSize
)
308 * Check if the next descriptor is free, in which case we
309 * extend it, otherwise we create a new free descriptor.
311 if (NextDesc
&& NextDesc
->Type
== UMA_FREE
)
313 /* Yes it is, expand its size and move it down */
314 NextDesc
->Size
+= (FoundUmaDesc
->Size
- RequestSize
);
315 NextDesc
->Start
-= (FoundUmaDesc
->Size
- RequestSize
);
319 // FIXME: It might be needed to consider a minimum size starting which we need to split.
320 // if (FoundUmaDesc->Size - RequestSize > (3 << 4))
322 /* Create a new free descriptor and insert it after the current one */
323 NewUmaDesc
= CreateUmaDescriptor(&FoundUmaDesc
->Entry
,
324 FoundUmaDesc
->Start
+ RequestSize
,
325 FoundUmaDesc
->Size
- RequestSize
,
329 DPRINT1("CreateUmaDescriptor failed, UMA descriptor list possibly corrupted!\n");
335 else // if (FoundUmaDesc->Size <= RequestSize)
339 /* Check whether the next descriptor is free and large enough for merging */
340 if (NextDesc
&& NextDesc
->Type
== UMA_FREE
&&
341 FoundUmaDesc
->Size
+ NextDesc
->Size
>= RequestSize
)
343 /* Yes it is, reduce its size and move it up, and enlarge the reallocated descriptor */
344 NextDesc
->Size
-= (RequestSize
- FoundUmaDesc
->Size
);
345 NextDesc
->Start
+= (RequestSize
- FoundUmaDesc
->Size
);
347 if (NextDesc
->Size
== 0) FreeUmaDescriptor(NextDesc
);
356 /* Finally, resize the descriptor */
357 FoundUmaDesc
->Size
= RequestSize
;
360 /* Returned size is in paragraphs */
361 *Size
= (FoundUmaDesc
->Size
>> 4);
367 /* Returned size is in paragraphs */
368 *Size
= (MaxSize
>> 4);
373 BOOLEAN
UmaMgrInitialize(VOID
)
376 #define ROM_AREA_START 0xE0000
377 #define ROM_AREA_END 0xFFFFF
379 #define OPTION_ROM_SIGNATURE 0xAA55
381 PUMA_DESCRIPTOR UmaDesc
= NULL
;
382 ULONG StartAddress
= 0;
384 UMA_DESC_TYPE Type
= UMA_FREE
;
393 // ULONG RomStart[] = {};
394 // ULONG RomEnd[] = {};
395 ULONG RomBoundaries
[] = {0xA0000, 0xC0000, /*0xC8000, 0xE0000,*/ 0xF0000, 0x100000};
396 ULONG SizeIncrement
[] = {0x20000, 0x00800, /*0x00800, 0x10000,*/ 0x10000, 0x0000 };
398 // InitializeListHead(&UmaDescriptorList);
400 /* NOTE: There must be always one UMA descriptor at least */
401 // FIXME: Maybe it should be a static object?
403 for (i
= 0; i
< ARRAYSIZE(RomBoundaries
) - 1; i
++)
405 Start
= RomBoundaries
[i
]; // RomStart[i]
406 End
= RomBoundaries
[i
+1]; // RomEnd[i]
407 Increment
= SizeIncrement
[i
];
409 for (Address
= Start
; Address
< End
; Address
+= Increment
)
411 if (StartAddress
== 0)
413 /* Initialize data for a new descriptor */
414 StartAddress
= Address
;
419 /* Is it a normal system zone/user-excluded zone? */
420 if (Address
>= 0xA0000 && Address
< 0xC0000)
422 // StartAddress = Address;
426 /* Create descriptor */
427 UmaDesc
= CreateUmaDescriptor(NULL
, StartAddress
, Size
, Type
);
428 if (!UmaDesc
) return FALSE
;
433 /* Is it the PC ROM BIOS? */
434 else if (Address
>= 0xF0000)
436 // StartAddress = Address;
437 Size
= 0x10000; // Increment;
440 /* Create descriptor */
441 UmaDesc
= CreateUmaDescriptor(NULL
, StartAddress
, Size
, Type
);
442 if (!UmaDesc
) return FALSE
;
447 /* Is it an option ROM? */
448 else if (Address
>= 0xC0000 && Address
< 0xF0000)
451 ULONG PrevRomAddress
= 0;
452 ULONG PrevRomSize
= 0;
454 // while (Address < 0xF0000)
455 for (; Address
< 0xF0000; Address
+= Increment
)
458 #if 0 // FIXME: Is this block, better here...
460 // We may be looping inside a ROM block, if: Type == 2 and:
461 // (StartAddress <= Address &&) StartAddress + Size > Address.
462 // In this case, do nothing (do not increase size either)
463 // But if we are now outside of a ROM block, then we need
464 // to create the previous block, and initialize a new empty one!
465 // (and following the next passages, increase its size).
467 // if (StartAddress < Address && Type != 2)
468 if (Type
== UMA_ROM
&& StartAddress
+ Size
> Address
)
470 /* We are inside ROM, do nothing */
472 else if (Type
== UMA_ROM
&& StartAddress
+ Size
<= Address
)
474 /* We finished a ROM descriptor */
476 /* Create descriptor */
477 UmaDesc
= CreateUmaDescriptor(NULL
, StartAddress
, Size
, Type
);
478 if (!UmaDesc
) return FALSE
;
483 else if (Type
!= UMA_ROM
)
491 /// if (Address >= 0xE0000) { Increment = 0x10000; }
493 if (StartAddress
== 0)
495 /* Initialize data for a new descriptor */
496 StartAddress
= Address
;
504 if (*(PUSHORT
)REAL_TO_PHYS(Address
) == OPTION_ROM_SIGNATURE
)
507 * If this is an adapter ROM (Start: C8000, End: E0000),
508 * its reported size is stored in byte 2 of the ROM.
510 * If this is an expansion ROM (Start: E0000, End: F0000),
511 * its real length is 64kB.
513 RomSize
= *(PUCHAR
)REAL_TO_PHYS(Address
+ 2) * 512;
514 // if (Address >= 0xE0000) RomSize = 0x10000;
515 if (Address
>= 0xE0000) { RomSize
= 0x10000; Increment
= RomSize
; }
517 DPRINT1("ROM present @ address 0x%p\n", Address
);
519 if (StartAddress
!= 0 && Size
!= 0 &&
520 StartAddress
+ Size
<= Address
)
522 /* Finish old descriptor */
523 UmaDesc
= CreateUmaDescriptor(NULL
, StartAddress
, Size
, Type
);
524 if (!UmaDesc
) return FALSE
;
528 * We may have overlapping ROMs, when PrevRomAddress + PrevRomSize > RomAddress.
529 * They must be put inside the same UMA descriptor.
531 if (PrevRomAddress
+ PrevRomSize
> /*Rom*/Address
)
536 * PrevRomAddress remains the same, but adjust
537 * PrevRomSize (ROM descriptors merging).
539 PrevRomSize
= max(PrevRomSize
, RomSize
+ Address
- PrevRomAddress
);
541 // FIX: Confirm that the start address is really
542 // the one of the previous descriptor.
543 StartAddress
= PrevRomAddress
;
549 // Non-overlapping ROM
551 PrevRomAddress
= Address
;
552 PrevRomSize
= RomSize
;
554 /* Initialize a new descriptor. We will create it when it's OK */
555 StartAddress
= Address
;
561 #if 1 // FIXME: ...or there??
564 // We may be looping inside a ROM block, if: Type == 2 and:
565 // (StartAddress <= Address &&) StartAddress + Size > Address.
566 // In this case, do nothing (do not increase size either)
567 // But if we are now outside of a ROM block, then we need
568 // to create the previous block, and initialize a new empty one!
569 // (and following the next passages, increase its size).
571 // if (StartAddress < Address && Type != UMA_ROM)
572 if (Type
== UMA_ROM
&& StartAddress
+ Size
> Address
)
574 // We are inside ROM, do nothing
576 else if (Type
== UMA_ROM
&& StartAddress
+ Size
<= Address
)
578 // We finished a ROM descriptor.
580 /* Create descriptor */
581 UmaDesc
= CreateUmaDescriptor(NULL
, StartAddress
, Size
, Type
);
582 if (!UmaDesc
) return FALSE
;
587 else if (Type
!= UMA_ROM
)
594 // Fixed incroment; we may encounter again overlapping ROMs, etc.
595 // Address += Increment;
598 if (StartAddress
!= 0 && Size
!= 0)
600 /* Create descriptor */
601 UmaDesc
= CreateUmaDescriptor(NULL
, StartAddress
, Size
, Type
);
602 if (!UmaDesc
) return FALSE
;
614 VOID
UmaMgrCleanup(VOID
)
616 PUMA_DESCRIPTOR UmaDesc
;
618 while (!IsListEmpty(&UmaDescriptorList
))
620 UmaDesc
= (PUMA_DESCRIPTOR
)CONTAINING_RECORD(UmaDescriptorList
.Flink
, UMA_DESCRIPTOR
, Entry
);
621 FreeUmaDescriptor(UmaDesc
);