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