Routix OS: blockcache.c Source File

00001 /* blockcache.c */
00002 
00003 
00004 /* 
00005  * El cache de bloques se encarga de interactuar entre los pedidos de los diferentes
00006  * filesystems y los drivers determinados, siendo su principal función la de mantener
00007  * un cache con los bloques más accedidos.
00008  * Presenta una lista de bloques libres y un hash accedido por device y sector lógico
00009  * que conduce a listas de bloques (sus headers más precisamente).
00010  * Existe otra lista de bloques libres (sin uso y utilizados pero de menor a mayor
00011  * tiempo de acceso LRU) donde puede haber bloques de listas pertenecientes al hash.
00012  *
00013  */
00014 
00015 #include <routix/device.h>
00016 #include <routix/kalloc.h>
00017 #include <routix/kstdio.h>
00018 #include <routix/task.h>
00019 #include <routix/system.h>
00020 #include <fs/blockcache.h>
00021 #include <sys/list.h>
00022 #include <routix/atomic.h>
00023 
00024 #define RUNSTATS 1
00025 
00026 
00027 #define PAGE_SIZE        4096
00028 
00029 #define MAXHASHENTRIES                  10
00030 #define HASH(maxhash,dev,sector)        ( (dev+sector)%maxhash )
00031 #define HASH_DEVICE(dev)                                        (dev)
00032 
00033 #define MAKE_MULTIPLE(original,multiple) ((original)+((multiple)-(original)%(multiple)))
00034 
00035 // Creamos los headers para manejar las listas de bloques libres y de hash.
00036 static LIST_NEW(block_cache_t)  free_list;
00037 static LIST_NEW(block_cache_t)  cached_list[MAXHASHENTRIES];
00038 static LIST_NEW(block_cache_t)  drv_req_list[MAXDEVICEENTRIES];
00039 
00040 
00041 // Esta función se encarga de prealocar los bloques y sus respectivos headers
00042 // de acuerdo a la cantidad de memoria total del sistema, utiliza la definición
00043 // de MAX_BLOCKCACHEMEM_PCT en system.h (dado en un valor porcentual).
00044 // NOTA: por ahora esta definición la dejo acá.
00045 //
00046 // Máximo uso de memoria por parte del cache de bloques: 5%
00047 #define MAX_BLOCKCACHE_MEM 5
00048 
00049 
00050 // Funciones locales
00051 static inline byte *alloc_block();
00052 static inline block_cache_t *alloc_header();
00053 static inline block_cache_t *getfreeblock(void);
00054 
00055 // Funciones locales de debug
00056 static void show_cached_list(void);
00057 
00058 
00059 void start_block_cache(int totalmemory)
00060 {
00061         int blocks;
00062         int tmp;
00063         //int pagesforblocks,pagesforheaders;
00064         
00065 
00066         // Inicializamos los headers de las listas free_list, cached_list y drv_req (drivers request)
00067         LIST_INIT(free_list);
00068 
00069         for (tmp=0; tmp<MAXHASHENTRIES; tmp++) {
00070                 LIST_INIT(cached_list[tmp]);
00071         }
00072 
00073         for (tmp=0; tmp<MAXDEVICEENTRIES; tmp++) {
00074                 LIST_INIT(drv_req_list[tmp]);
00075         }
00076         
00077         // Transformamos la cantidad de memoria de Mb a bytes
00078         totalmemory *= 1024*1024;
00079 
00080         // Calcalumos la cantidad de bloques (redondeando hacia abajo),
00081         // pero teniendo en cuenta que un bloque posee 512 bytes entrarán
00082         // 8 bloques por página, por lo tanto redondemos la cantidad de
00083         // blocks de modo que sea múltiplo de 8
00084         blocks=totalmemory*MAX_BLOCKCACHE_MEM/(100*BLOCK_SIZE);
00085         blocks=MAKE_MULTIPLE(blocks,PAGE_SIZE/BLOCK_SIZE);
00086 
00087         // Un bloque es de 512bytes, por lo tanto en una página entran 8 bloques
00088         //pagesforblocks=blocks/8;
00089 
00090         // Oks, ahora veamos, la cantidad de headers es igual a la cantidad de bloques,
00091         // pero su tamaño es de sizeof(buffer_block_t), o sea que necesitaremos:
00092         // memoria_headers=blocks*sizeof(buffer_block_t)
00093         // y en páginas de 4KB:
00094         // memoria_headers_pag=roundup(memoria_headers/4096)
00095         // y redondeamos para arriba
00096         //pagesforheaders=blocks*sizeof(buffer_block_t)/4096 + ( (blocks*sizeof(buffer_block_t))%4096 ) ? 1 : 0;
00097         kprintf("Inicializando Cache de Bloques con %d bloques\n",blocks);
00098         byte *datablock;
00099         block_cache_t *headerblock;
00100         
00101         while ( blocks-- ) {
00102 
00103                 // Alocamos un bloque de datos
00104                 datablock=alloc_block();
00105 
00106                 // su correspondiente header
00107                 headerblock=alloc_header();
00108 
00109                 // los vinculamos
00110                 BLOCK_CACHE_BUFFER(headerblock)=datablock;
00111                 BLOCK_CACHE_STATE(headerblock)=UNLOCKED;
00112                 BLOCK_CACHE_LOCKCOUNT(headerblock)=0;
00113                 LIST_CLEAN(BLOCK_CACHE_PENDING_PROCESS_LIST(headerblock));
00114 
00115 
00116                 // y lo agregamos a la lista de bloques libres
00117                 LIST_ADD(free_list,free,headerblock);
00118 
00119         }
00120         
00121 }
00122 
00123 
00124 inline static byte *alloc_block()
00125 {
00126         static byte *actual_page=NULL;
00127         static unsigned short int used_blocks=0;
00128 
00129         if ( (actual_page==NULL) || (used_blocks == (PAGE_SIZE/BLOCK_SIZE)) ) {
00130                 actual_page=(byte *) kmalloc_page();
00131                 used_blocks=0;
00132         }
00133 
00134         return( (byte *) (actual_page+BLOCK_SIZE*(used_blocks++)) );
00135 
00136 }
00137 
00138 inline static block_cache_t *alloc_header()
00139 {
00140         static block_cache_t *actual_page=NULL;
00141         static unsigned short int used_headers=0;
00142 
00143         if ( (actual_page==NULL) || (used_headers >= (PAGE_SIZE/sizeof(block_cache_t))) ) {
00144                 actual_page=(block_cache_t *) kmalloc_page();
00145                 used_headers=0;
00146         }
00147 
00148         used_headers++;
00149 
00150         return(actual_page++);
00151 }
00152 
00153 // Oks, le devolvemos el primer request
00154 inline block_cache_t *getrequest(device_t device)
00155 {
00156 
00157         // El primer request en la lista
00158         return( LIST_FIRST(drv_req_list[HASH_DEVICE(device)]) );
00159 }
00160 
00161 // El floppy nos devolvió el control, ahora debemos analizar su respuesta
00162 inline void endrequest(block_cache_t *block)
00163 {
00164         // Lo eliminamos de la lista de request
00165         LIST_DEL(drv_req_list[HASH_DEVICE( BLOCK_CACHE_DEVICE(block) )],driver_request_list,block);
00166 
00167         // despertamos al proceso que generó la solicitud (es el primero en la lista)
00168         despertar_task( LIST_FIRST(BLOCK_CACHE_PENDING_PROCESS_LIST(block)) );
00169                         
00170 }
00171 
00176 inline void sendrequest(block_cache_t *block)
00177 {
00178         // Agregamos el bloque a la lista de solicitudes correspondiente
00179         // al dispositivo
00180         LIST_ADD_TAIL(drv_req_list[ HASH_DEVICE( BLOCK_CACHE_DEVICE(block) ) ],driver_request_list,block);
00181 
00182         // Activa el flag que indica tarea para un determinado driver, por ahora no hace nada
00183         
00184 }
00185 
00186 
00287 int cache_read(device_t device, word sector, unsigned int start, char *dstbuffer, unsigned int len)
00288 {
00289 
00290         block_cache_t *tmp;
00291         task_struct_t *proc_iterator;
00292 
00293         #ifdef RUNSTATS
00294         long long counter;
00295 
00296         if ( getvar("debugcache") == 1 ) 
00297                 kprintf("cache_read: starting, dev: %d, sector: %d, start: %d buffer: 0x%x len: %d\n",device,sector,start,dstbuffer,len);
00298 
00299         if ( getvar("debugcache") == 2 )
00300                 rdtscl(counter);
00301         #endif
00302 
00303         restart:
00304 
00305         if ( getvar("debugcache") == 1 )
00306                 kprintf("cache_read: buscando bloque en la lista de cache\n");
00307 
00308         START_ATOMIC_OPERATION;
00309 
00310         #ifdef RUNSTATS
00311         if ( getvar("debugcache")==1 )
00312                 show_cached_list();
00313         #endif
00314         
00315         // Primero buscamos si ya existe el bloque en la lista del cache
00316         LIST_FOREACH(tmp,cached_list[ HASH(MAXHASHENTRIES,device,sector) ], cached)
00317                 if ( BLOCK_CACHE_DEVICE(tmp)==device && BLOCK_CACHE_SECTOR(tmp)==sector )
00318                         break;
00319 
00320         // Está cacheado ?
00321         if ( tmp ) {
00322 
00323                 #ifdef RUNSTATS
00324                 if ( getvar("debugcache") == 1 )
00325                         kprintf("cache_read: cache hit !\n");
00326                 #endif
00327 
00328                 // Esta tomado por alguien más
00329                 if ( BLOCK_CACHE_STATE(tmp)==WRITE_LOCKED || BLOCK_CACHE_STATE(tmp)==SYNCRONIZING ) {
00330 
00331                         // Colocamos el proceso actual al final de la lista de procesos con IO pendiente (el primer
00332                         // nodo es el proceso original que solicitó la IO)
00333                         LIST_ADD_TAIL(BLOCK_CACHE_PENDING_PROCESS_LIST(tmp),io_pending,actual);
00334 
00335 
00336                         // Ponemos a dormir la tarea
00337                         dormir_task(actual);
00338 
00339                         FINISH_ATOMIC_OPERATION;
00340 
00341                         // Rescheduleamos
00342                         _reschedule();
00343 
00344                         // Oks, en este punto alguien nos despertó, volvemos a intentar tomar el bloque
00345                         // (odio los goto ! :P pero en este momento es una salida rápida y permite no
00346                         // oscurecer el código.
00347                         goto restart;
00348                 }
00349 
00350                 // Se encuentra disponible
00351                 else {
00352         
00353                         // Si esta deslockeado lo lockeamos, inicializamos la cuenta de locks a cero
00354                         // y lo quitamos de la lista de bloques free
00355                         if ( BLOCK_CACHE_STATE(tmp)==UNLOCKED ) {
00356                                 BLOCK_CACHE_STATE(tmp)=READ_LOCKED;
00357                                 LIST_DEL(free_list,free,tmp);
00358                                 BLOCK_CACHE_LOCKCOUNT(tmp)=0;
00359                         }
00360                         #ifdef RUNSTATS
00361                         else {
00362                                 if ( getvar("debugcache")==3 )
00363                                 kprintf("Sector: %d relockeando!\n",sector);
00364                                 //show_cached_list();
00365                         }
00366                         #endif
00367 
00368                 }
00369 
00370         }
00371 
00372         // No está cacheado
00373         else {
00374 
00375                 #ifdef RUNSTATS
00376                 if ( getvar("debugcache") == 1 )
00377                         kprintf("cache_read: cache miss(%d) ",sector);
00378                 #endif
00379 
00380 
00381                 // Obtenemos un bloque de la lista free
00382                 tmp=getfreeblock();
00383 
00384                 #ifdef RUNSTATS
00385                 if ( getvar("debugcache") == 1 )
00386                         kprintf("cache_read: bloque obtenido de la free list 0x%x\n",tmp);
00387 
00388                 if ( getvar("debugcache") == 1 )
00389                         kprintf("cache_read: eliminamos este nuevo bloque de la free list\n");
00390                 #endif
00391 
00392                 // lo marcamos en Sincronización
00393                 BLOCK_CACHE_STATE(tmp)=SYNCRONIZING;
00394 
00395                 // Seteamos el dispositivo, sector y operacion
00396                 BLOCK_CACHE_DEVICE(tmp)=device;
00397                 BLOCK_CACHE_SECTOR(tmp)=sector;
00398                 BLOCK_CACHE_OPERATION(tmp)=IOREAD;
00399 
00400 
00401                 #ifdef RUNSTATS
00402                 if ( getvar("debugcache") == 1 ) {
00403                         kprintf("cache_read: lo LOCKEAMOS\n");
00404             kprintf("cache_read: entrada numero %d en la cached list\n",HASH(MAXHASHENTRIES,device,sector));
00405                 }
00406                 #endif
00407                 
00408                 // y lo insertamos en la lista de bloques cacheados
00409                 LIST_ADD_TAIL(cached_list[ HASH(MAXHASHENTRIES,device,sector) ],cached,tmp);
00410 
00411 
00412                 #ifdef RUNSTATS
00413                 if ( getvar("debugcache") == 1 )
00414                         kprintf("cache_read: y lo insertamos al final de la lista de bloques cacheados\n");
00415                 #endif
00416 
00417                 // colocamos el proceso actual al principio de la lista de procesos con IO pendiente
00418                 LIST_ADD(BLOCK_CACHE_PENDING_PROCESS_LIST(tmp),io_pending,actual);
00419 
00420                 #ifdef RUNSTATS
00421                 if ( getvar("debugcache") == 1 ) {
00422                         kprintf("cache_read: insertamos el proceso actual en la lista de procesos con io pendiente\n");
00423                         kprintf("cache_read: enviamos el request\n");
00424                 }
00425                 #endif
00426 
00427                 // Realizamos el request, en este punto, sendrequest pondrá a dormir el
00428                 // proceso actual hasta que se complete la petición.
00429                 sendrequest(tmp);
00430 
00431                 // Ponemos a dormir la tarea
00432                 dormir_task(actual);
00433 
00434                 #ifdef RUNSTATS
00435                 if ( getvar("debugcache") == 1 )
00436                         kprintf("cache_read: nos dormimos\n");
00437                 #endif
00438 
00439                 FINISH_ATOMIC_OPERATION;
00440 
00441                 // Rescheduleamos
00442                 _reschedule();
00443 
00444                 START_ATOMIC_OPERATION;
00445 
00446                 #ifdef RUNSTATS
00447                 if ( getvar("debugcache") == 1 )
00448                         kprintf("cache_read: nos despertamos !\n");
00449                 #endif
00450 
00451                 // lo quitamos de la lista de procesos io pending
00452                 LIST_DEL(BLOCK_CACHE_PENDING_PROCESS_LIST(tmp),io_pending,actual);
00453 
00454                 // despertar al resto de los procesos en espera de este bloque
00455                 LIST_FOREACH(proc_iterator,BLOCK_CACHE_PENDING_PROCESS_LIST(tmp),io_pending) {
00456                         despertar_task(proc_iterator);
00457                 }
00458 
00459                 // vaciar la lista de procesos en estado IO
00460                 LIST_CLEAN(BLOCK_CACHE_PENDING_PROCESS_LIST(tmp));
00461 
00462 
00463                 // El dispositivo concluyó su trabajo, por lo tanto recuperamos el control en este punto.
00464                 //
00465                 // si falló debemos:
00466                 //              1. quitarlo de la lista de bloques cacheados
00467                 //              2. colocarlo al ppio de la lista de bloques libres
00468                 //              3. retornar error (-1)
00469                 if ( BLOCK_CACHE_RETURN(tmp) == -1 ) {
00470 
00471                         LIST_DEL(cached_list[ HASH(MAXHASHENTRIES,device,sector) ],cached,tmp);
00472 
00473                         LIST_ADD(free_list,free,tmp);
00474 
00475                         FINISH_ATOMIC_OPERATION;
00476 
00477                         return -1;
00478 
00479                 }
00480 
00481         }
00482 
00483         // Incrementamos la cantidad de locks en él
00484         BLOCK_CACHE_LOCKCOUNT(tmp)++;
00485 
00486         // lo marcamos READ_LOCKED
00487         BLOCK_CACHE_STATE(tmp)=READ_LOCKED;
00488 
00489         FINISH_ATOMIC_OPERATION;
00490 
00491         char *origin = BLOCK_CACHE_BUFFER(tmp) + start;
00492 
00493         // Copiamos los datos leidos al buffer del proceso
00494         while ( len-- )
00495                 *dstbuffer++ = *origin++;
00496 
00497         START_ATOMIC_OPERATION;
00498 
00499         // Decrementamos la cantidad de locks en él
00500         BLOCK_CACHE_LOCKCOUNT(tmp)--;
00501 
00502         if ( BLOCK_CACHE_LOCKCOUNT(tmp)==0 ) {
00503                 
00504                 // Deslockeamos el bloque
00505                 BLOCK_CACHE_STATE(tmp)=UNLOCKED;
00506 
00507                 // Lo colocamos al final de la free list
00508                 LIST_ADD_TAIL(free_list,free,tmp);
00509 
00510                 // Despertamos todos los procesos que están esperando por el bloque
00511                 // y vaciamos la lista
00512                 LIST_FOREACH(proc_iterator,BLOCK_CACHE_PENDING_PROCESS_LIST(tmp),io_pending)
00513                         despertar_task(proc_iterator);
00514 
00515                 LIST_CLEAN(BLOCK_CACHE_PENDING_PROCESS_LIST(tmp));
00516 
00517         }
00518 
00519         #ifdef RUNSTATS
00520   if ( getvar("debugcache") == 2 ) {
00521                 long long int counterfinal;
00522                 rdtscl(counterfinal);
00523                 kprintf("0x%llx ",counterfinal-counter);
00524         }
00525         #endif
00526 
00527         FINISH_ATOMIC_OPERATION;
00528 
00529         return 1;
00530 
00531 }
00532 
00533 
00562 static inline block_cache_t *getfreeblock(void)
00563 {
00564 
00565         byte found=0;
00566         block_cache_t *tmp;
00567         
00568         do {
00569 
00570                 // Obtenemos el pri             
00571                 tmp=LIST_FIRST(free_list);
00572 
00573                 // y lo quitamos de ella
00574                 LIST_DEL(free_list,free,tmp);
00575 
00576                 // Bloque marcado como modificado
00577                 if ( BLOCK_CACHE_STATE(tmp)==DIRTY ) {
00578                         // proximo a agregar, manejo de escritura asincrónica
00579                 }
00580 
00581                 // Bloque disponible
00582                 else
00583                         found=1;
00584                 
00585         } while ( ! found );
00586 
00587         return tmp;
00588 
00589 }
00590 
00591 
00592 static void show_cached_list(void)
00593 {
00594         int iter;
00595         block_cache_t *tmp;
00596         char state;
00597 
00598         int cached_blocks=0;
00599 
00600         for(iter=0; iter<MAXHASHENTRIES; iter++) {
00601 
00602                 kprintf("Entry %d: ",iter);
00603 
00604                 LIST_FOREACH(tmp,cached_list[iter],cached) {
00605                         cached_blocks++;
00606                         
00607                         switch ( BLOCK_CACHE_STATE(tmp) ) {
00608 
00609                                 case READ_LOCKED:
00610                                                                                                         state='R';
00611                                                                                                         break;
00612 
00613                                 case WRITE_LOCKED:
00614                                                                                                         state='W';
00615                                                                                                         break;
00616                                                                                                         
00617                                 case UNLOCKED:
00618                                                                                                         state='U';
00619                                                                                                         break;
00620 
00621                                 case SYNCRONIZING:
00622                                                                                                         state='S';
00623                                                                                                         break;
00624 
00625                                 default:
00626                                                                                                         state='?';
00627                                                                                                         break;
00628                                                                                                         
00629 
00630                         }
00631 
00632                         if ( BLOCK_CACHE_STATE(tmp)==READ_LOCKED ) {
00633                                 kprintf(" %d(%c%d)", BLOCK_CACHE_SECTOR(tmp),state,BLOCK_CACHE_LOCKCOUNT(tmp));
00634                         }
00635                         else {
00636                                 kprintf(" %d(%c)", BLOCK_CACHE_SECTOR(tmp),state);
00637                         }
00638                 }
00639 
00640                 kprintf("\n");
00641 
00642         }
00643 
00644         kprintf("%d bloques cacheados\n",cached_blocks);
00645                 
00646 }