- Main Page
- Modules
- Data Structures
- Files

- Search for |

# vram.c

    00001 /*
    00002  * Helper for use with the PSP Software Development Kit - http://www.pspdev.org
    00003  * -----------------------------------------------------------------------
    00004  * Licensed under GPL
    00005  *
    00006  * vram.c - Standard C high performance VRAM allocation routines.
    00007  *
    00008  * Copyright (c) 2007 Alexander Berl 'Raphael' <raphael@fx-world.org>
    00009  * http://wordpress.fx-world.org
    00010  *
    00011  *
    00012  * This program is free software; you can redistribute it and/or modify
    00013  * it under the terms of the GNU General Public License as published by
    00014  * the Free Software Foundation; either version 2 of the License, or
    00015  * (at your option) any later version.
    00016  *
    00017  * This program is distributed in the hope that it will be useful,
    00018  * but WITHOUT ANY WARRANTY; without even the implied warranty of
    00019  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    00020  * GNU General Public License for more details.
    00021  *
    00022  * You should have received a copy of the GNU General Public License
    00023  * along with this program; if not, write to the Free Software
    00024  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
    00025  */
    00026
    00027 #include "vlib.h"
    00028
    00029 // Configure the memory to be managed
    00030 #define __MEM_SIZE 0x00200000
    00031 #define __MEM_START 0x04000000
    00032
    00033 // Configure the block size the memory gets subdivided into (page size)
    00034 // __MEM_SIZE/__BLOCK_SIZE may not exceed 2^15 = 32768
    00035 // The block size also defines the alignment of allocations
    00036 // Larger block sizes perform better, because the blocktable is smaller and therefore fits better into cache
    00037 // however the overhead is also bigger and more memory is wasted
    00038 #define __BLOCK_SIZE 512
    00039 #define __MEM_BLOCKS (__MEM_SIZE/__BLOCK_SIZE)
    00040 #define __BLOCKS(x) ((x+__BLOCK_SIZE-1)/__BLOCK_SIZE)
    00041 #define __BLOCKSIZE(x) ((x+__BLOCK_SIZE-1)&~(__BLOCK_SIZE-1))
    00042
    00043
    00044 // A MEMORY BLOCK ENTRY IS MADE UP LIKE THAT:
    00045 // bit:  31     32    30 - 15    14-0
    00046 //    free   block    prev     size
    00047 //
    00048 // bit 31: free bit, indicating if block is allocated or not
    00049 // bit 30: blocked bit, indicating if block is part of a larger block (0) - used for error resilience
    00050 // bit 30-15: block index of previous block
    00051 // bit 14- 0: size of current block
    00052 //
    00053 // This management can handle a max amount of 2^15 = 32768 blocks, which resolves to 32MB at blocksize of 1024 bytes
    00054 //
    00055 #define __BLOCK_GET_SIZE(x)    ((x & 0x7FFF))
    00056 #define __BLOCK_GET_PREV(x)    ((x >> 15) & 0x7FFF)
    00057 #define __BLOCK_GET_FREE(x)    ((x >> 31))
    00058 #define __BLOCK_GET_BLOCK(x)   ((x >> 30) & 0x1)
    00059 #define __BLOCK_SET_SIZE(x,y)  x=((x & ~0x7FFF) | ((y) & 0x7FFF))
    00060 #define __BLOCK_ADD_SIZE(x,y)  x=((x & ~0x7FFF) | (((x & 0x7FFF)+((y) & 0x7FFF)) & 0x7FFF))
    00061 #define __BLOCK_SET_PREV(x,y)  x=((x & ~0x3FFF8000) | (((y) & 0x7FFF)<<15))
    00062 #define __BLOCK_SET_FREE(x,y)  x=((x & 0x7FFFFFFF) | (((y) & 0x1)<<31))
    00063 #define __BLOCK_SET_BLOCK(x,y) x=((x & 0xBFFFFFFF) | (((y) & 0x1)<<30))
    00064 #define __BLOCK_MAKE(s,p,f,n)   (((f & 0x1)<<31) | ((n & 0x1)<<30) | (((p) & 0x7FFF)<<15) | ((s) & 0x7FFF))
    00065 #define __BLOCK_GET_FREEBLOCK(x) ((x>>30) & 0x3)    // returns 11 if block is a starting block and free, 10 if block is a starting block and allocated, 0x if it is a non-starting block (don't change)
    00066 #define __BLOCK0 ((__MEM_BLOCKS) | (1<<31) | (1<<30))
    00067
    00068
    00069 unsigned int  __mem_blocks[__MEM_BLOCKS] = { 0 };
    00070
    00071
    00072 static int __largest_update = 0;
    00073 static int __largest_block = __MEM_BLOCKS;
    00074 static int __mem_free = __MEM_BLOCKS;
    00075
    00076
    00077 inline void* vrelptr ( void *ptr ) {
    00078   return ( void* ) ( ( u32 ) ptr & ~__MEM_START );
    00079 }
    00080
    00081 inline void* vabsptr ( void *ptr ) {
    00082   return ( void* ) ( ( u32 ) ptr | __MEM_START );
    00083 }
    00084
    00085
    00086 static void __find_largest_block() {
    00087   int i = 0;
    00088   __largest_block = 0;
    00089   while ( i < __MEM_BLOCKS ) {
    00090     int csize = __BLOCK_GET_SIZE ( __mem_blocks[i] );
    00091     if ( __BLOCK_GET_FREEBLOCK ( __mem_blocks[i] ) == 3 && csize > __largest_block )
    00092       __largest_block = csize;
    00093     i += csize;
    00094   }
    00095   __largest_update = 0;
    00096 }
    00097
    00098 #ifdef _DEBUG
    00099 void __memwalk() {
    00100   int i = 0;
    00101   if ( __mem_blocks[0] == 0 ) __mem_blocks[0] = __BLOCK0;
    00102   while ( i < __MEM_BLOCKS ) {
    00103     printf ( "BLOCK %i:\n", i );
    00104     printf ( "  free: %i\n", __BLOCK_GET_FREEBLOCK ( __mem_blocks[i] ) );
    00105     printf ( "  size: %i\n", __BLOCK_GET_SIZE ( __mem_blocks[i] ) );
    00106     printf ( "  prev: %i\n", __BLOCK_GET_PREV ( __mem_blocks[i] ) );
    00107     i += __BLOCK_GET_SIZE ( __mem_blocks[i] );
    00108   }
    00109 }
    00110 #endif
    00111
    00112 void* valloc ( size_t size ) {
    00113   // Initialize memory block, if not yet done
    00114   if ( __mem_blocks[0] == 0 ) __mem_blocks[0] = __BLOCK0;
    00115
    00116   int i = 0;
    00117   int j = 0;
    00118   int bsize = __BLOCKS ( size );
    00119
    00120   if ( __largest_update == 0 && __largest_block < bsize ) {
    00121 #ifdef _DEBUG
    00122     printf ( "Not enough memory to allocate %i bytes (largest: %i)!\n", size, vlargestblock() );
    00123 #endif
    00124     return ( 0 );
    00125   }
    00126
    00127 #ifdef _DEBUG
    00128   printf ( "allocating %i bytes, in %i blocks\n", size, bsize );
    00129 #endif
    00130   // Find smallest block that still fits the requested size
    00131   int bestblock = -1;
    00132   int bestblock_prev = 0;
    00133   int bestblock_size = __MEM_BLOCKS + 1;
    00134   while ( i < __MEM_BLOCKS ) {
    00135     int csize = __BLOCK_GET_SIZE ( __mem_blocks[i] );
    00136     if ( __BLOCK_GET_FREEBLOCK ( __mem_blocks[i] ) == 3 && csize >= bsize ) {
    00137       if ( csize < bestblock_size ) {
    00138         bestblock = i;
    00139         bestblock_prev = j;
    00140         bestblock_size = csize;
    00141       }
    00142
    00143       if ( csize == bsize )
    00144         break;
    00145     }
    00146     j = i;
    00147     i += csize;
    00148   }
    00149
    00150   if ( bestblock < 0 ) {
    00151 #ifdef _DEBUG
    00152     printf ( "Not enough memory to allocate %i bytes (largest: %i)!\n", size, vlargestblock() );
    00153 #endif
    00154     return ( 0 );
    00155   }
    00156
    00157   i = bestblock;
    00158   j = bestblock_prev;
    00159   int csize = __BLOCK_GET_SIZE ( __mem_blocks[i] );
    00160   __mem_blocks[i] = __BLOCK_MAKE ( bsize, j, 0, 1 );
    00161
    00162   int next = i + bsize;
    00163   if ( csize > bsize && next < __MEM_BLOCKS ) {
    00164     __mem_blocks[next] = __BLOCK_MAKE ( csize - bsize, i, 1, 1 );
    00165     int nextnext = i + csize;
    00166     if ( nextnext < __MEM_BLOCKS ) {
    00167       __BLOCK_SET_PREV ( __mem_blocks[nextnext], next );
    00168     }
    00169   }
    00170
    00171   __mem_free -= bsize;
    00172   if ( __largest_block == csize ) {
    00173     if ( ( csize - bsize ) > ( __MEM_BLOCKS / 2 ) )
    00174       __largest_block = ( csize - bsize );
    00175     else
    00176       __largest_update = 1; // if we just allocated from one of the largest blocks
    00177   }
    00178   return ( ( void* ) ( __MEM_START + ( i*__BLOCK_SIZE ) ) );
    00179 }
    00180
    00181
    00182 void vfree ( void* ptr ) {
    00183   if ( ptr == 0 ) return;
    00184
    00185   int block = ( ( unsigned int ) ptr - __MEM_START ) / __BLOCK_SIZE;
    00186   if ( block < 0 || block > __MEM_BLOCKS ) {
    00187 #ifdef _DEBUG
    00188     printf ( "Block is out of range: %i (0x%x)\n", block, ( int ) ptr );
    00189 #endif
    00190     return;
    00191   }
    00192   int csize = __BLOCK_GET_SIZE ( __mem_blocks[block] );
    00193 #ifdef _DEBUG
    00194   printf ( "freeing block %i (0x%x), size: %i\n", block, ( int ) ptr, csize );
    00195 #endif
    00196
    00197   if ( __BLOCK_GET_FREEBLOCK ( __mem_blocks[block] ) != 1 || csize == 0 ) {
    00198 #ifdef _DEBUG
    00199     printf ( "Block was not allocated!\n" );
    00200 #endif
    00201     return;
    00202   }
    00203
    00204   // Mark block as free
    00205   __BLOCK_SET_FREE ( __mem_blocks[block], 1 );
    00206   __mem_free += csize;
    00207
    00208   int next = block + csize;
    00209   // Merge with previous block if possible
    00210   int prev = __BLOCK_GET_PREV ( __mem_blocks[block] );
    00211   if ( prev < block ) {
    00212     if ( __BLOCK_GET_FREEBLOCK ( __mem_blocks[prev] ) == 3 ) {
    00213       __BLOCK_ADD_SIZE ( __mem_blocks[prev], csize );
    00214       __BLOCK_SET_BLOCK ( __mem_blocks[block], 0 ); // mark current block as inter block
    00215       if ( next < __MEM_BLOCKS )
    00216         __BLOCK_SET_PREV ( __mem_blocks[next], prev );
    00217       block = prev;
    00218     }
    00219   }
    00220
    00221   // Merge with next block if possible
    00222   if ( next < __MEM_BLOCKS ) {
    00223     if ( __BLOCK_GET_FREEBLOCK ( __mem_blocks[next] ) == 3 ) {
    00224       __BLOCK_ADD_SIZE ( __mem_blocks[block], __BLOCK_GET_SIZE ( __mem_blocks[next] ) );
    00225       __BLOCK_SET_BLOCK ( __mem_blocks[next], 0 );  // mark next block as inter block
    00226       int nextnext = next + __BLOCK_GET_SIZE ( __mem_blocks[next] );
    00227       if ( nextnext < __MEM_BLOCKS )
    00228         __BLOCK_SET_PREV ( __mem_blocks[nextnext], block );
    00229     }
    00230   }
    00231
    00232   // Update if a new largest block emerged
    00233   if ( __largest_block < __BLOCK_GET_SIZE ( __mem_blocks[block] ) ) {
    00234     __largest_block = __BLOCK_GET_SIZE ( __mem_blocks[block] );
    00235     __largest_update = 0;   // No update necessary any more, because update only necessary when largest has shrinked at most
    00236   }
    00237 }
    00238
    00239
    00240 size_t vmemavail() {
    00241   return __mem_free * __BLOCK_SIZE;
    00242 }
    00243
    00244
    00245 size_t vlargestblock() {
    00246   if ( __largest_update ) __find_largest_block();
    00247   return __largest_block * __BLOCK_SIZE;
    00248 }