# kmalloc.c

Go to the documentation of this file.

    00001 /*****************************************************************************************
    00002  Copyright (c) 2002-2004 The UbixOS Project
    00003  All rights reserved.
    00004
    00005  Redistribution and use in source and binary forms, with or without modification, are
    00006  permitted provided that the following conditions are met:
    00007
    00008  Redistributions of source code must retain the above copyright notice, this list of
    00009  conditions, the following disclaimer and the list of authors.  Redistributions in binary
    00010  form must reproduce the above copyright notice, this list of conditions, the following
    00011  disclaimer and the list of authors in the documentation and/or other materials provided
    00012  with the distribution. Neither the name of the UbixOS Project nor the names of its
    00013  contributors may be used to endorse or promote products derived from this software
    00014  without specific prior written permission.
    00015
    00016  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
    00017  EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
    00018  MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
    00019  THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
    00020  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
    00021  OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
    00022  HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
    00023  TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
    00024  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    00025
    00026  $Id: kmalloc_8c-source.html 88 2016-01-12 00:11:29Z reddawg $
    00027
    00028 *****************************************************************************************/
    00029
    00030 #include <lib/kmalloc.h>
    00031 #include <lib/kprintf.h>
    00032 #include <ubixos/kpanic.h>
    00033 #include <ubixos/sched.h>
    00034 #include <ubixos/spinlock.h>
    00035 #include <vmm/vmm.h>
    00036 #include <string.h>
    00037 #include <assert.h>
    00038
    00039 /*
    00040  Set up three descriptor tables:
    00041
    00042  kernDesc      - The inuse descriptor table
    00043  freeKernDesc  - The free descriptor table (descriptors with memory backing just not in use)
    00044  emptyKernDesc - The empty descriptor table (descriptors with out a memory backing)
    00045
    00046 */
    00047 static struct memDescriptor *usedKernDesc  = 0x0;
    00048 static struct memDescriptor *freeKernDesc  = 0x0;
    00049 static struct memDescriptor *emptyKernDesc = 0x0;
    00050
    00051 /*
    00052  Set up our spinlocks so we do not corrupt linked lists if we have re-entrancy
    00053 */
    00054 static spinLock_t mallocSpinLock    = SPIN_LOCK_INITIALIZER;
    00055 static spinLock_t emptyDescSpinLock = SPIN_LOCK_INITIALIZER;
    00056
    00057 /************************************************************************
    00058
    00059 Function: void *getEmptyDesc()
    00060 Description: Find An Empty Descriptor
    00061
    00062 Notes:
    00063
    00064 02/17/03 - Is This Efficient?
    00065
    00066 ************************************************************************/
    00067 static void *getEmptyDesc() {
    00068   int i = 0x0;
    00069   struct memDescriptor *tmpDesc = 0x0;
    00070
    00071   spinLock(&emptyDescSpinLock);
    00072
    00073   tmpDesc = emptyKernDesc;
    00074
    00075   if (tmpDesc != 0x0) {
    00076     emptyKernDesc       = tmpDesc->next;
    00077     if (emptyKernDesc != 0x0)
    00078       emptyKernDesc->prev = 0x0;
    00079
    00080
    00081     tmpDesc->next       = 0x0;
    00082     tmpDesc->prev       = 0x0;
    00083     spinUnlock(&emptyDescSpinLock);
    00084     return(tmpDesc);
    00085     }
    00086   if ((emptyKernDesc = (struct memDescriptor *)vmm_getFreeMallocPage(4)) == 0x0)
    00087     kpanic("Error: vmmGetFreeKernelPage returned NULL\n");
    00088
    00089   /* zero out the memory so we know there is no garbage */
    00090   memset(emptyKernDesc,0x0,0x4000);
    00091
    00092   emptyKernDesc[0].next = &emptyKernDesc[1];
    00093
    00094   for (i = 0x1;i < ((0x4000/sizeof(struct memDescriptor)));i++) {
    00095     if (i+1 < (0x4000/sizeof(struct memDescriptor)))
    00096       emptyKernDesc[i].next = &emptyKernDesc[i+1];
    00097     else
    00098       emptyKernDesc[i].next = 0x0;
    00099     emptyKernDesc[i].prev = &emptyKernDesc[i-1];
    00100     }
    00101
    00102   tmpDesc = &emptyKernDesc[0];
    00103
    00104   emptyKernDesc       = tmpDesc->next;
    00105   emptyKernDesc->prev = 0x0;
    00106   tmpDesc->next       = 0x0;
    00107   tmpDesc->prev       = 0x0;
    00108   spinUnlock(&emptyDescSpinLock);
    00109   return(tmpDesc);
    00110   }
    00111
    00112 /************************************************************************
    00113
    00114 Function: void insertFreeDesc(struct memDescriptor *freeDesc)
    00115 Description: This Function Inserts A Free Descriptor On The List Which Is
    00116              Kept In Size Order
    00117
    00118 Notes:
    00119
    00120 02/17/03 - This Was Inspired By TCA's Great Wisdom -
    00121            "[20:20:59] <TCA> You should just insert it in order"
    00122
    00123 ************************************************************************/
    00124 static int insertFreeDesc(struct memDescriptor *freeDesc) {
    00125   struct memDescriptor *tmpDesc = 0x0;
    00126   assert(freeDesc);
    00127
    00128   if (freeDesc->limit <= 0x0)
    00129     kpanic("Inserting Descriptor with no limit\n");
    00130
    00131   if (freeKernDesc != 0x0) {
    00132
    00133     #if 0
    00134     freeDesc->next = freeKernDesc;
    00135     freeDesc->prev = 0x0;
    00136     freeKernDesc->prev = freeDesc;
    00137     freeKernDesc = freeDesc;
    00138     #endif
    00139
    00140     for (tmpDesc = freeKernDesc;tmpDesc != 0x0;tmpDesc = tmpDesc->next) {
    00141       if (freeDesc->limit <= tmpDesc->limit) {
    00142
    00143         freeDesc->prev = tmpDesc->prev;
    00144         if (tmpDesc->prev != 0x0)
    00145           tmpDesc->prev->next = freeDesc;
    00146
    00147
    00148         tmpDesc->prev  = freeDesc;
    00149         freeDesc->next = tmpDesc;
    00150
    00151         if (tmpDesc == freeKernDesc)
    00152           freeKernDesc = freeDesc;
    00153         return(0x0);
    00154         }
    00155        if (tmpDesc->next == 0x0) {
    00156          tmpDesc->next = freeDesc;
    00157          freeDesc->prev = tmpDesc;
    00158          freeDesc->next = 0x0;
    00159          return(0x0);
    00160          }
    00161       }
    00162     kpanic("didnt Insert\n");
    00163     return(0x0);
    00164     }
    00165   else {
    00166     freeDesc->prev = 0x0;
    00167     freeDesc->next = 0x0;
    00168     freeKernDesc = freeDesc;
    00169     return(0x0);
    00170     }
    00171
    00172   return(0x1);
    00173   }
    00174
    00175 /************************************************************************
    00176
    00177 Function: void mergeMemBlocks()
    00178 Description: This Function Will Merge Free Blocks And Free Pages
    00179
    00180 Notes:
    00181
    00182 03/05/03 - We Have A Problem It Seems The First Block Is Limit 0x0
    00183
    00184 ************************************************************************/
    00185 static void mergeMemBlocks() {
    00186   struct memDescriptor *tmpDesc1 = 0x0;
    00187   struct memDescriptor *tmpDesc2 = 0x0;
    00188   uInt32               baseAddr  = 0x0;
    00189
    00190   return;
    00191
    00192   //Loop The Free Descriptors See If We Can Merge Them
    00193   mergeStart:
    00194   for (tmpDesc1=freeKernDesc;tmpDesc1 != 0x0;tmpDesc1=tmpDesc1->next) {
    00195     /*
    00196      Compare The Base Addr With The Other Descriptors If You Find The One
    00197      That You Are Looking For Lets Merge Them
    00198     */
    00199     if (tmpDesc1->limit != 0x0) {
    00200       baseAddr = (uInt32)tmpDesc1->baseAddr + (uInt32)tmpDesc1->limit;
    00201       for (tmpDesc2=freeKernDesc;tmpDesc2;tmpDesc2=tmpDesc2->next) {
    00202         if ((uInt32)tmpDesc2->baseAddr == baseAddr) {
    00203           tmpDesc1->limit += tmpDesc2->limit;
    00204           tmpDesc2->baseAddr = 0x0;
    00205           tmpDesc2->limit    = 0x0;
    00206           if (tmpDesc2->prev) {
    00207             tmpDesc2->prev->next = tmpDesc2->next;
    00208             }
    00209           if (tmpDesc2->next) {
    00210             tmpDesc2->next->prev = tmpDesc2->prev;
    00211             }
    00212           tmpDesc2->prev      = 0x0;
    00213           tmpDesc2->next      = emptyKernDesc;
    00214           emptyKernDesc->prev = tmpDesc2;
    00215           emptyKernDesc       = tmpDesc2;
    00216           if (tmpDesc1->prev) {
    00217             tmpDesc1->prev->next = tmpDesc1->next;
    00218             }
    00219           if (tmpDesc1->next) {
    00220             tmpDesc1->next->prev = tmpDesc1->prev;
    00221             }
    00222           tmpDesc1->prev = 0x0;
    00223           tmpDesc1->next = 0x0;
    00224           kprintf("mergememBlocks: [%i]\n",tmpDesc1->limit);
    00225           insertFreeDesc(tmpDesc1);
    00226           //tmpDesc1 = freeKernDesc;
    00227           goto mergeStart;
    00228           break;
    00229           }
    00230         }
    00231       }
    00232     }
    00233   return;
    00234   }
    00235
    00236
    00237 /************************************************************************
    00238
    00239 Function: void *kmalloc(uInt32 len)
    00240 Description: Allocate Kernel Memory
    00241
    00242 Notes:
    00243
    00244 02/17/03 - Do I Still Need To Pass In The Pid?
    00245
    00246 ************************************************************************/
    00247 void *kmalloc(uInt32 len) {
    00248   struct memDescriptor *tmpDesc1 = 0x0;
    00249   struct memDescriptor *tmpDesc2 = 0x0;
    00250   char                 *buf      = 0x0;
    00251   int                   i        = 0x0;
    00252   uInt16                pages    = 0x0;
    00253
    00254
    00255   spinLock(&mallocSpinLock);
    00256
    00257   len = MALLOC_ALIGN(len);
    00258
    00259
    00260   if (len == 0x0) {
    00261     spinUnlock(&mallocSpinLock);
    00262         kprintf("kmalloc: len = 0!\n");
    00263     return(0x0);
    00264     }
    00265   for (tmpDesc1 = freeKernDesc;tmpDesc1 != 0x0;tmpDesc1=tmpDesc1->next) {
    00266     assert(tmpDesc1);
    00267     if (tmpDesc1->limit >= len) {
    00268       if (tmpDesc1->prev != 0x0)
    00269         tmpDesc1->prev->next = tmpDesc1->next;
    00270       if (tmpDesc1->next != 0x0)
    00271         tmpDesc1->next->prev = tmpDesc1->prev;
    00272
    00273       if (tmpDesc1 == freeKernDesc)
    00274         freeKernDesc = tmpDesc1->next;
    00275
    00276       tmpDesc1->prev = 0x0;
    00277       tmpDesc1->next = usedKernDesc;
    00278       if (usedKernDesc != 0x0)
    00279         usedKernDesc->prev = tmpDesc1;
    00280       usedKernDesc = tmpDesc1;
    00281       if (tmpDesc1->limit > len) {
    00282         tmpDesc2 = getEmptyDesc();
    00283         assert(tmpDesc2);
    00284         tmpDesc2->limit = tmpDesc1->limit - len;
    00285         tmpDesc1->limit = len;
    00286         tmpDesc2->baseAddr = tmpDesc1->baseAddr + len;
    00287         tmpDesc2->next = 0x0;
    00288         tmpDesc2->prev = 0x0;
    00289         insertFreeDesc(tmpDesc2);
    00290         }
    00291       buf = (char *)tmpDesc1->baseAddr;
    00292       for (i=0;i<tmpDesc1->limit;i++) {
    00293         (char)buf[i] = (char)0x0;
    00294         }
    00295       spinUnlock(&mallocSpinLock);
    00296       //kprintf("m1[%i:%i:0x%X]",tmpDesc1->limit,len,tmpDesc1->baseAddr);
    00297         assert(tmpDesc1->baseAddr);
    00298       return(tmpDesc1->baseAddr);
    00299       }
    00300     }
    00301   tmpDesc1 = getEmptyDesc();
    00302   //kprintf("no empty desc\n");
    00303   if (tmpDesc1 != 0x0) {
    00304     pages = ((len + 4095)/4096);
    00305     tmpDesc1->baseAddr = (struct memDescriptor *)vmm_getFreeMallocPage(pages);
    00306     tmpDesc1->limit    = len;
    00307     tmpDesc1->next     = usedKernDesc;
    00308     tmpDesc1->prev     = 0x0;
    00309     if (usedKernDesc != 0x0)
    00310       usedKernDesc->prev       = tmpDesc1;
    00311     usedKernDesc             = tmpDesc1;
    00312
    00313     if (((pages * 4096)-len) > 0x0) {
    00314       tmpDesc2           = getEmptyDesc();
    00315       assert(tmpDesc2);
    00316       tmpDesc2->baseAddr = tmpDesc1->baseAddr + tmpDesc1->limit;
    00317       tmpDesc2->limit    = ((pages * 4096)-len);
    00318       tmpDesc2->prev     = 0x0;
    00319       tmpDesc2->next     = 0x0;
    00320       if (tmpDesc2->limit <= 0x0)
    00321         kprintf("kmalloc-2 tmpDesc2: [%i]\n",tmpDesc2->limit);
    00322       insertFreeDesc(tmpDesc2);
    00323       }
    00324
    00325       buf = (char *)tmpDesc1->baseAddr;
    00326       for (i=0;i<tmpDesc1->limit;i++) {
    00327         (char)buf[i] = (char)0x0;
    00328         }
    00329     spinUnlock(&mallocSpinLock);
    00330     //kprintf("baseAddr2[0x%X:0x%X]",tmpDesc1,tmpDesc1->baseAddr);
    00331     //kprintf("m2[%i:%i:0x%X]",tmpDesc1->limit,len,tmpDesc1->baseAddr);
    00332         assert(tmpDesc1->baseAddr);
    00333     return(tmpDesc1->baseAddr);
    00334     }
    00335   //Return Null If Unable To Malloc
    00336   spinUnlock(&mallocSpinLock);
    00337   //kprintf("baseAddr3[0x0]");
    00338   return(0x0);
    00339   }
    00340
    00341 /************************************************************************
    00342
    00343 Function: void kfree(void *baseAddr)
    00344 Description: This Will Find The Descriptor And Free It
    00345
    00346 Notes:
    00347
    00348 02/17/03 - I need To Make It Join Descriptors
    00349
    00350 ************************************************************************/
    00351 void kfree(void *baseAddr) {
    00352   struct memDescriptor *tmpDesc = 0x0;
    00353
    00354   if (baseAddr == 0x0) return;
    00355   assert(baseAddr);
    00356
    00357   assert(usedKernDesc);
    00358   spinLock(&mallocSpinLock);
    00359
    00360   for (tmpDesc = usedKernDesc;tmpDesc != 0x0;tmpDesc = tmpDesc->next) {
    00361
    00362     if (tmpDesc->baseAddr == baseAddr) {
    00363       memset(tmpDesc->baseAddr,0xBE,tmpDesc->limit);
    00364
    00365       if (usedKernDesc == tmpDesc)
    00366         usedKernDesc = tmpDesc->next;
    00367
    00368       if (tmpDesc->prev != 0x0)
    00369         tmpDesc->prev->next = tmpDesc->next;
    00370
    00371       if (tmpDesc->next != 0x0)
    00372         tmpDesc->next->prev = tmpDesc->prev;
    00373
    00374
    00375       tmpDesc->next = 0x0;
    00376       tmpDesc->prev = 0x0;
    00377
    00378       if (tmpDesc->limit <= 0x0)
    00379         kprintf("kfree tmpDesc1: [%i]\n",tmpDesc->limit);
    00380       //kprintf("{0x%X}",tmpDesc->baseAddr);
    00381       insertFreeDesc(tmpDesc);
    00382
    00383      // mergeMemBlocks();
    00384       spinUnlock(&mallocSpinLock);
    00385       return;
    00386       }
    00387     }
    00388   spinUnlock(&mallocSpinLock);
    00389   kprintf("Kernel: Error Freeing Descriptor! [0x%X]\n",(uInt32)baseAddr);
    00390   return;
    00391   }
    00392
    00393 /***
    00394  $Log: kmalloc_8c-source.html,v $
    00394  Revision 1.7  2006/12/15 17:47:06  reddawg
    00394  Updates
    00394
    00395  Revision 1.3  2006/12/05 14:10:21  reddawg
    00396  Workign Distro
    00397
    00398  Revision 1.2  2006/10/06 15:48:01  reddawg
    00399  Starting to make ubixos work with UFS2
    00400
    00401  Revision 1.1.1.1  2006/06/01 12:46:16  reddawg
    00402  ubix2
    00403
    00404  Revision 1.4  2006/06/01 12:42:09  reddawg
    00405  Getting back to the basics
    00406
    00407  Revision 1.3  2006/06/01 03:58:33  reddawg
    00408  wondering about this stuff here
    00409
    00410  Revision 1.2  2005/10/12 00:13:37  reddawg
    00411  Removed
    00412
    00413  Revision 1.1.1.1  2005/09/26 17:24:11  reddawg
    00414  no message
    00415
    00416  Revision 1.35  2005/08/04 18:32:59  fsdfs
    00417
    00418  added error reporting
    00419
    00420  Revision 1.34  2005/08/04 18:23:41  reddawg
    00421  BUG: Assert has issues that must be looked into
    00422
    00423  Revision 1.33  2005/08/04 17:11:11  fsdfs
    00424
    00425  ----------------------------------------
    00426
    00427  -------------------
    00428
    00429  Revision 1.32  2004/09/28 21:50:04  reddawg
    00430  kmalloc: now when we kfree memory is filled with 0xBE so it is easy to debug if we continue to use free'd memory
    00431
    00432  Revision 1.31  2004/09/19 16:17:25  reddawg
    00433  fixed memory leak we now lose no memory....
    00434
    00435  Revision 1.30  2004/09/14 21:51:24  reddawg
    00436  Debug info
    00437
    00438  Revision 1.29  2004/09/11 23:39:31  reddawg
    00439  ok time for bed
    00440
    00441  Revision 1.28  2004/09/11 23:21:26  reddawg
    00442  run now do you get fegfaults with BB?
    00443
    00444  Revision 1.27  2004/09/11 22:49:28  reddawg
    00445  pat look at lines 276-285  does the math seem right?
    00446
    00447  Revision 1.26  2004/09/11 22:33:13  reddawg
    00448  minor changes
    00449
    00450  Revision 1.25  2004/09/11 12:11:11  reddawg
    00451  Cleaning up the VFS more changes to follow...
    00452
    00453  Revision 1.24  2004/09/08 23:19:58  reddawg
    00454  hmm
    00455
    00456  Revision 1.23  2004/09/06 15:13:25  reddawg
    00457  Last commit before FreeBSD 6.0
    00458
    00459  Revision 1.22  2004/08/26 22:51:18  reddawg
    00460  TCA touched me :( i think he likes men....
    00461
    00462
    00463  sched.h:        kTask_t added parentPid
    00464  endtask.c:     fixed term back to parentPid
    00465  exec.c:          cleaned warnings
    00466  fork.c:            fixed term to childPid
    00467  sched.c:         clean up for dead tasks
    00468  systemtask.c: clean up dead tasks
    00469  kmalloc.c:       cleaned up warnings
    00470  udp.c:            cleaned up warnings
    00471  bot.c:             cleaned up warnings
    00472  shell.c:           cleaned up warnings
    00473  tcpdump.c:     took a dump
    00474  hd.c:             cleaned up warnings
    00475  ubixfs.c:        stopped prning debug info
    00476
    00477  Revision 1.21  2004/07/28 15:05:43  reddawg
    00478  Major:
    00479    Pages now have strict security enforcement.
    00480    Many null dereferences have been resolved.
    00481    When apps loaded permissions set for pages rw and ro
    00482
    00483  Revision 1.20  2004/07/28 00:17:05  reddawg
    00484  Major:
    00485    Disconnected page 0x0 from the system... Unfortunately this broke many things
    00486    all of which have been fixed. This was good because nothing deferences NULL
    00487    any more.
    00488
    00489  Things affected:
    00490    malloc,kmalloc,getfreepage,getfreevirtualpage,pagefault,fork,exec,ld,ld.so,exec,file
    00491
    00492  Revision 1.19  2004/07/26 19:15:49  reddawg
    00493  test code, fixes and the like
    00494
    00495  Revision 1.18  2004/07/26 16:52:45  reddawg
    00496  here we go
    00497
    00498  Revision 1.17  2004/07/24 23:04:44  reddawg
    00499  Changes... mark let me know if you fault at pid 185 when you type stress
    00500
    00501  Revision 1.16  2004/07/21 10:02:09  reddawg
    00502  devfs: renamed functions
    00503  device system: renamed functions
    00504  fdc: fixed a few potential bugs and cleaned up some unused variables
    00505  strol: fixed definition
    00506  endtask: made it print out freepage debug info
    00507  kmalloc: fixed a huge memory leak we had some unhandled descriptor insertion so some descriptors were lost
    00508  ld: fixed a pointer conversion
    00509  file: cleaned up a few unused variables
    00510  sched: broke task deletion
    00511  kprintf: fixed ogPrintf definition
    00512
    00513  Revision 1.15  2004/07/20 23:20:50  reddawg
    00514  kmalloc: forgot to remove an assert
    00515
    00516  Revision 1.14  2004/07/20 23:18:11  reddawg
    00517  Made malloc a little more robust but we have a serious memory leak somewhere
    00518
    00519  Revision 1.13  2004/07/20 22:29:55  reddawg
    00520  assert: remade assert
    00521
    00522  Revision 1.12  2004/07/20 18:58:24  reddawg
    00523  Few fixes
    00524
    00525  Revision 1.11  2004/07/18 05:24:15  reddawg
    00526  Fixens
    00527
    00528  Revision 1.10  2004/07/17 18:00:47  reddawg
    00529  kmalloc: added assert()
    00530
    00531  Revision 1.9  2004/07/17 15:54:52  reddawg
    00532  kmalloc: added assert()
    00533  bioscall: fixed some potential problem by not making 16bit code
    00534  paging: added assert()
    00535
    00536  Revision 1.8  2004/06/17 14:50:32  reddawg
    00537  kmalloc: converted some variables to static
    00538
    00539  Revision 1.7  2004/06/17 02:54:54  flameshadow
    00540  chg: fixed cast
    00541
    00542  Revision 1.6  2004/05/26 11:56:51  reddawg
    00543  kmalloc: fixed memrgeMemBlocks hopefully it will prevent future segfault issues
    00544           by not having any more overlapping blocks
    00545
    00546  Revision 1.5  2004/05/25 14:01:14  reddawg
    00547  Implimented Better Spinlocking No More Issues With KMALLOC which actually
    00548  was causing bizzare problems
    00549
    00550  END
    00551  ***/
    00552