DOSBox-X
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines
src/misc/regionalloctracking.cpp
00001 
00002 #include <assert.h>
00003 #include "dosbox.h"
00004 #include "mem.h"
00005 #include "cpu.h"
00006 #include "bios.h"
00007 #include "regs.h"
00008 #include "cpu.h"
00009 #include "callback.h"
00010 #include "inout.h"
00011 #include "pic.h"
00012 #include "hardware.h"
00013 #include "pci_bus.h"
00014 #include "joystick.h"
00015 #include "mouse.h"
00016 #include "callback.h"
00017 #include "setup.h"
00018 #include "serialport.h"
00019 #include "mapper.h"
00020 #include "vga.h"
00021 #include "regionalloctracking.h"
00022 #include "parport.h"
00023 #include <time.h>
00024 #include <sys/timeb.h>
00025 
00026 /* Really, Microsoft, Really?? You're the only compiler I know that doesn't understand ssize_t! */
00027 #if defined(_MSC_VER)
00028 #include <basetsd.h>
00029 typedef SSIZE_T ssize_t;
00030 #endif
00031 
00032 RegionAllocTracking::Block::Block() : start(0), end(0), free(true) {
00033 }
00034 
00035 RegionAllocTracking::RegionAllocTracking() : _min(0), _max(~((Bitu)0)), topDownAlloc(false) {
00036 }
00037 
00038 Bitu RegionAllocTracking::getMemory(Bitu bytes,const char *who,Bitu alignment,Bitu must_be_at) {
00039         if (bytes == 0u) return alloc_failed;
00040         if (alignment > 1u && must_be_at != 0u) return alloc_failed; /* avoid nonsense! */
00041         if (who == NULL) who = "";
00042         if (alist.empty()) E_Exit("getMemory called when '%s' allocation list not initialized",name.c_str());
00043 
00044         /* alignment must be power of 2 */
00045         if (alignment == 0u)
00046                 alignment = 1u;
00047         else if ((alignment & (alignment-1u)) != 0u)
00048                 E_Exit("getMemory called with non-power of 2 alignment value %u on '%s'",(int)alignment,name.c_str());
00049 
00050         {
00051                 /* allocate downward from the top */
00052                 size_t si = topDownAlloc ? (alist.size() - 1u) : 0u;
00053                 while ((ssize_t)si >= 0) {
00054                         Block &blk = alist[si];
00055                         Bitu base;
00056 
00057                         if (!blk.free || (blk.end+1u-blk.start) < bytes) {
00058                                 if (topDownAlloc) si--;
00059                                 else si++;
00060                                 continue;
00061                         }
00062 
00063                         /* if must_be_at != 0 the caller wants a block at a very specific location */
00064                         if (must_be_at != 0) {
00065                                 /* well, is there room to fit the forced block? if it starts before
00066                                  * this block or the forced block would end past the block then, no. */
00067                                 if (must_be_at < blk.start || (must_be_at+bytes-1u) > blk.end) {
00068                                         if (topDownAlloc) si--;
00069                                         else si++;
00070                                         continue;
00071                                 }
00072 
00073                                 base = must_be_at;
00074                                 if (base == blk.start && (base+bytes-1u) == blk.end) { /* easy case: perfect match */
00075                                         blk.free = false;
00076                                         blk.who = who;
00077                                 }
00078                                 else if (base == blk.start) { /* need to split */
00079                                         Block newblk = blk; /* this becomes the new block we insert */
00080                                         blk.start = base+bytes;
00081                                         newblk.end = base+bytes-1u;
00082                                         newblk.free = false;
00083                                         newblk.who = who;
00084                                         alist.insert(alist.begin()+(std::vector<RegionAllocTracking::Block>::difference_type)si,newblk);
00085                                 }
00086                                 else if ((base+bytes-1) == blk.end) { /* need to split */
00087                                         Block newblk = blk; /* this becomes the new block we insert */
00088                                         blk.end = base-1;
00089                                         newblk.start = base;
00090                                         newblk.free = false;
00091                                         newblk.who = who;
00092                                         alist.insert(alist.begin()+(std::vector<RegionAllocTracking::Block>::difference_type)si+1u,newblk);
00093                                 }
00094                                 else { /* complex split */
00095                                         Block newblk = blk,newblk2 = blk; /* this becomes the new block we insert */
00096                                         Bitu orig_end = blk.end;
00097                                         blk.end = base-1u;
00098                                         newblk.start = base+bytes;
00099                                         newblk.end = orig_end;
00100                                         alist.insert(alist.begin()+(std::vector<RegionAllocTracking::Block>::difference_type)si+1u,newblk);
00101                                         newblk2.start = base;
00102                                         newblk2.end = base+bytes-1u;
00103                                         newblk2.free = false;
00104                                         newblk2.who = who;
00105                                         alist.insert(alist.begin()+(std::vector<RegionAllocTracking::Block>::difference_type)si+1u,newblk2);
00106                                 }
00107                         }
00108                         else {
00109                                 if (topDownAlloc) {
00110                                         base = blk.end + 1u - bytes; /* allocate downward from the top */
00111                                         assert(base >= blk.start);
00112                                 }
00113                                 else {
00114                                         base = blk.start; /* allocate upward from the bottom */
00115                                         assert(base <= blk.end);
00116                                         base += alignment - 1u; /* alignment round up */
00117                                 }
00118 
00119                                 base &= ~(alignment - 1u); /* NTS: alignment == 16 means ~0xF or 0xFFFF0 */
00120                                 if (base < blk.start || (base+bytes-1u) > blk.end) { /* if not possible after alignment, then skip */
00121                                         if (topDownAlloc) si--;
00122                                         else si++;
00123                                         continue;
00124                                 }
00125 
00126                                 if (topDownAlloc) {
00127                                         /* easy case: base matches start, just take the block! */
00128                                         if (base == blk.start) {
00129                                                 blk.free = false;
00130                                                 blk.who = who;
00131                                                 return blk.start;
00132                                         }
00133 
00134                                         /* not-so-easy: need to split the block and claim the upper half */
00135                                         RegionAllocTracking::Block newblk = blk; /* this becomes the new block we insert */
00136                                         newblk.start = base;
00137                                         newblk.free = false;
00138                                         newblk.who = who;
00139                                         blk.end = base - 1u;
00140 
00141                                         if (blk.start > blk.end) {
00142                                                 sanityCheck();
00143                                                 abort();
00144                                         }
00145 
00146                                         alist.insert(alist.begin()+(std::vector<RegionAllocTracking::Block>::difference_type)si+1,newblk);
00147                                 }
00148                                 else {
00149                                         if ((base+bytes-1u) == blk.end) {
00150                                                 blk.free = false;
00151                                                 blk.who = who;
00152                                                 return blk.start;
00153                                         }
00154 
00155                                         /* not-so-easy: need to split the block and claim the lower half */
00156                                         RegionAllocTracking::Block newblk = blk; /* this becomes the new block we insert */
00157                                         newblk.start = base+bytes;
00158                                         blk.free = false;
00159                                         blk.who = who;
00160                                         blk.end = base+bytes-1u;
00161 
00162                                         if (blk.start > blk.end) {
00163                                                 sanityCheck();
00164                                                 abort();
00165                                         }
00166 
00167                                         alist.insert(alist.begin()+(std::vector<RegionAllocTracking::Block>::difference_type)si+1u,newblk);
00168                                 }
00169                         }
00170 
00171                         LOG(LOG_BIOS,LOG_DEBUG)("getMemory in '%s' (0x%05x bytes,\"%s\",align=%u,mustbe=0x%05x) = 0x%05x",name.c_str(),(int)bytes,who,(int)alignment,(int)must_be_at,(int)base);
00172                         sanityCheck();
00173                         return base;
00174                 }
00175         }
00176 
00177         LOG(LOG_BIOS,LOG_DEBUG)("getMemory in '%s' (0x%05x bytes,\"%s\",align=%u,mustbe=0x%05x) = FAILED",name.c_str(),(int)bytes,who,(int)alignment,(int)must_be_at);
00178         sanityCheck();
00179         return alloc_failed;
00180 }
00181 
00182 Bitu RegionAllocTracking::getMinAddress() {
00183         size_t si = 0;
00184         Bitu r = _max;
00185 
00186         while (si < alist.size()) {
00187                 Block &blk = alist[si];
00188                 if (blk.free) {
00189                         si++;
00190                         continue;
00191                 }
00192 
00193                 r = blk.start;
00194                 break;
00195         }
00196 
00197         return r;
00198 }
00199 
00200 void RegionAllocTracking::initSetRange(Bitu start,Bitu end) {
00201         Block x;
00202 
00203         assert(start <= end);
00204 
00205         alist.clear();
00206         _min = start;
00207         _max = end;
00208 
00209         x.end = _max;
00210         x.free = true;
00211         x.start = _min;
00212         alist.push_back(x);
00213 }
00214 
00215 void RegionAllocTracking::logDump() {
00216         size_t si;
00217 
00218         LOG(LOG_MISC,LOG_DEBUG)("%s dump:",name.c_str());
00219         for (si=0;si < alist.size();si++) {
00220                 Block &blk = alist[si];
00221                 LOG(LOG_MISC,LOG_DEBUG)("     0x%08x-0x%08x free=%u %s",(int)blk.start,(int)blk.end,blk.free?1:0,blk.who.c_str());
00222         }
00223         LOG(LOG_MISC,LOG_DEBUG)("[end dump]");
00224 }
00225 
00226 void RegionAllocTracking::sanityCheck() {
00227         Block *pblk,*blk;
00228         size_t si;
00229 
00230         if (alist.size() <= 1)
00231                 return;
00232 
00233         pblk = &alist[0];
00234         for (si=1;si < alist.size();si++) {
00235                 blk = &alist[si];
00236                 if (blk->start != (pblk->end+1) || blk->start > blk->end || blk->start < _min || blk->end > _max) {
00237                         LOG(LOG_MISC,LOG_DEBUG)("RegionAllocTracking sanity check failure in '%s'",name.c_str());
00238                         logDump();
00239                         E_Exit("ROMBIOS sanity check failed");
00240                 }
00241 
00242                 pblk = blk;
00243         }
00244 }
00245 
00246 Bitu RegionAllocTracking::freeUnusedMinToLoc(Bitu phys) {
00247         if (phys <= _min) return _min;
00248         if ((_max+(Bitu)1) != (Bitu)0 && phys > (_max+1)) phys = _max+1;
00249 
00250         /* scan bottom-up */
00251         while (alist.size() != 0) {
00252                 RegionAllocTracking::Block &blk = alist[0];
00253                 if (!blk.free) {
00254                         if (phys > blk.start) phys = blk.start;
00255                         break;
00256                 }
00257                 if (phys > blk.end) {
00258                         /* remove entirely */
00259                         alist.erase(alist.begin());
00260                         continue;
00261                 }
00262                 if (phys <= blk.start) break;
00263                 blk.start = phys;
00264                 break;
00265         }
00266 
00267         assert(phys >= _min);
00268         assert(_max == (Bitu)0 || phys < _max);
00269         return phys;
00270 }
00271 
00272 void RegionAllocTracking::compactFree() {
00273         size_t si=0;
00274 
00275         while ((si+1u) < alist.size()) {
00276                 RegionAllocTracking::Block &blk1 = alist[si];
00277                 RegionAllocTracking::Block &blk2 = alist[si+1u];
00278 
00279                 if (blk1.free && blk2.free) {
00280                         if ((blk1.end+(Bitu)1u) == blk2.start) {
00281                                 blk1.end = blk2.end;
00282                                 alist.erase(alist.begin()+(std::vector<RegionAllocTracking::Block>::difference_type)si+1u);
00283                                 continue;
00284                         }
00285                 }
00286 
00287                 si++;
00288         }
00289 
00290         sanityCheck();
00291 }
00292 
00293 bool RegionAllocTracking::freeMemory(Bitu offset) {
00294         size_t si=0;
00295 
00296         if (offset < _min || offset > _max)
00297                 return false;
00298 
00299         while (si < alist.size()) {
00300                 RegionAllocTracking::Block &blk = alist[si];
00301 
00302                 if (offset >= blk.start && offset <= blk.end) {
00303                         LOG(LOG_BIOS,LOG_DEBUG)("freeMemory in '%s' (address=0x%08lx block='%s' range=0x%08lx-0x%08lx) success",
00304                                 name.c_str(),(unsigned long)offset,blk.who.c_str(),(unsigned long)blk.start,(unsigned long)blk.end);
00305 
00306                         if (!blk.free) {
00307                                 blk.free = true;
00308                                 blk.who.clear();
00309                                 compactFree();
00310                         }
00311 
00312                         return true;
00313                 }
00314 
00315                 si++;
00316         }
00317 
00318         LOG(LOG_BIOS,LOG_DEBUG)("freeMemory in '%s' (address=0x%08lx) FAILED",name.c_str(),(unsigned long)offset);
00319         return false;
00320 }
00321