Fork me on GitHub

root/mm/page.c

/* [previous][next][first][last][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. insert_to_hash
  2. remove_from_hash
  3. insert_on_free_list
  4. remove_from_free_list
  5. page_lock
  6. page_unlock
  7. get_free_page
  8. search_page_hash
  9. release_page
  10. is_valid_page
  11. update_page_cache
  12. write_page
  13. bread_page
  14. file_read
  15. page_init

   1 /*
   2  * fiwix/mm/page.c
   3  *
   4  * Copyright 2018-2021, Jordi Sanfeliu. All rights reserved.
   5  * Distributed under the terms of the Fiwix License.
   6  */
   7 
   8 /*
   9  * page.c implements a cache with a free list as a doubly circular linked
  10  * list and a chained hash table with doubly linked lists.
  11  *
  12  * hash table
  13  * +--------+  +--------------+  +--------------+  +--------------+
  14  * | index  |  |prev|data|next|  |prev|data|next|  |prev|data|next|
  15  * |   0   --> | /  |    | --->  <--- |    | --->  <--- |    |  / |
  16  * +--------+  +--------------+  +--------------+  +--------------+
  17  * +--------+  +--------------+  +--------------+  +--------------+
  18  * | index  |  |prev|data|next|  |prev|data|next|  |prev|data|next|
  19  * |   1   --> | /  |    | --->  <--- |    | --->  <--- |    |  / |
  20  * +--------+  +--------------+  +--------------+  +--------------+
  21  *              (page)            (page)            (page)  
  22  *    ...
  23  */
  24 
  25 #include <fiwix/asm.h>
  26 #include <fiwix/kernel.h>
  27 #include <fiwix/mm.h>
  28 #include <fiwix/mman.h>
  29 #include <fiwix/bios.h>
  30 #include <fiwix/sleep.h>
  31 #include <fiwix/sched.h>
  32 #include <fiwix/devices.h>
  33 #include <fiwix/buffer.h>
  34 #include <fiwix/errno.h>
  35 #include <fiwix/stdio.h>
  36 #include <fiwix/string.h>
  37 
  38 #define PAGE_HASH(inode, offset)        (((__ino_t)(inode) ^ (__off_t)(offset)) % (NR_PAGE_HASH))
  39 #define NR_PAGES        (page_table_size / sizeof(struct page))
  40 #define NR_PAGE_HASH    (page_hash_table_size / sizeof(unsigned int))
  41 
  42 struct page *page_table;                /* page pool */
  43 struct page *page_head;                 /* page pool head */
  44 struct page **page_hash_table;
  45 
  46 static void insert_to_hash(struct page *pg)
  47 {
  48         struct page **h;
  49         int i;
  50 
  51         i = PAGE_HASH(pg->inode, pg->offset);
  52         h = &page_hash_table[i];
  53 
  54         if(!*h) {
  55                 *h = pg;
  56                 (*h)->prev_hash = (*h)->next_hash = NULL;
  57         } else {
  58                 pg->prev_hash = NULL;
  59                 pg->next_hash = *h;
  60                 (*h)->prev_hash = pg;
  61                 *h = pg;
  62         }
  63         kstat.cached += (PAGE_SIZE / 1024);
  64 }
  65 
  66 static void remove_from_hash(struct page *pg)
  67 {
  68         struct page **h;
  69         int i;
  70 
  71         if(!pg->inode) {
  72                 return;
  73         }
  74 
  75         i = PAGE_HASH(pg->inode, pg->offset);
  76         h = &page_hash_table[i];
  77 
  78         while(*h) {
  79                 if(*h == pg) {
  80                         if((*h)->next_hash) {
  81                                 (*h)->next_hash->prev_hash = (*h)->prev_hash;
  82                         }
  83                         if((*h)->prev_hash) {
  84                                 (*h)->prev_hash->next_hash = (*h)->next_hash;
  85                         }
  86                         if(h == &page_hash_table[i]) {
  87                                 *h = (*h)->next_hash;
  88                         }
  89                         kstat.cached -= (PAGE_SIZE / 1024);
  90                         break;
  91                 }
  92                 h = &(*h)->next_hash;
  93         }
  94 }
  95 
  96 static void insert_on_free_list(struct page *pg)
  97 {
  98         if(!page_head) {
  99                 pg->prev_free = pg->next_free = pg;
 100                 page_head = pg;
 101         } else {
 102                 pg->next_free = page_head;
 103                 pg->prev_free = page_head->prev_free;
 104                 page_head->prev_free->next_free = pg;
 105                 page_head->prev_free = pg;
 106         }
 107 
 108         kstat.free_pages++;
 109 }
 110 
 111 static void remove_from_free_list(struct page *pg)
 112 {
 113         if(!kstat.free_pages) {
 114                 return;
 115         }
 116 
 117         pg->prev_free->next_free = pg->next_free;
 118         pg->next_free->prev_free = pg->prev_free;
 119         kstat.free_pages--;
 120         if(pg == page_head) {
 121                 page_head = pg->next_free;
 122         }
 123 
 124         if(!kstat.free_pages) {
 125                 page_head = NULL;
 126         }
 127 }
 128 
 129 void page_lock(struct page *pg)
 130 {
 131         unsigned long int flags;
 132 
 133         for(;;) {
 134                 SAVE_FLAGS(flags); CLI();
 135                 if(pg->flags & PAGE_LOCKED) {
 136                         RESTORE_FLAGS(flags);
 137                         sleep(&pg, PROC_UNINTERRUPTIBLE);
 138                 } else {
 139                         break;
 140                 }
 141         }
 142         pg->flags |= PAGE_LOCKED;
 143         RESTORE_FLAGS(flags);
 144 }
 145 
 146 void page_unlock(struct page *pg)
 147 {
 148         unsigned long int flags;
 149 
 150         SAVE_FLAGS(flags); CLI();
 151         pg->flags &= ~PAGE_LOCKED;
 152         wakeup(pg);
 153         RESTORE_FLAGS(flags);
 154 }
 155 
 156 struct page * get_free_page(void)
 157 {
 158         unsigned long int flags;
 159         struct page *pg;
 160 
 161         /* if no more pages on free list */
 162         if(!kstat.free_pages) {
 163                 /* reclaim some memory from buffer cache */
 164                 wakeup(&kswapd);
 165                 sleep(&get_free_page, PROC_UNINTERRUPTIBLE);
 166 
 167                 if(!kstat.free_pages) {
 168                         /* definitely out of memory! (no more pages) */
 169                         printk("%s(): pid %d ran out of memory. OOM killer needed!\n", __FUNCTION__, current->pid);
 170                         return NULL;
 171                 }
 172         }
 173 
 174         SAVE_FLAGS(flags); CLI();
 175 
 176         pg = page_head;
 177         remove_from_free_list(pg);
 178         remove_from_hash(pg);   /* remove it from its old hash */
 179         pg->count = 1;
 180         pg->inode = 0;
 181         pg->offset = 0;
 182         pg->dev = 0;
 183 
 184         RESTORE_FLAGS(flags);
 185         return pg;
 186 }
 187 
 188 struct page * search_page_hash(struct inode *inode, __off_t offset)
 189 {
 190         struct page *pg;
 191         int i;
 192 
 193         i = PAGE_HASH(inode->inode, offset);
 194         pg = page_hash_table[i];
 195 
 196         while(pg) {
 197                 if(pg->inode == inode->inode && pg->offset == offset && pg->dev == inode->dev) {
 198                         if(!pg->count) {
 199                                 remove_from_free_list(pg);
 200                         }
 201                         pg->count++;
 202                         return pg;
 203                 }
 204                 pg = pg->next_hash;
 205         }
 206 
 207         return NULL;
 208 }
 209 
 210 void release_page(int page)
 211 {
 212         unsigned long int flags;
 213         struct page *pg;
 214 
 215         if(!is_valid_page(page)) {
 216                 PANIC("Unexpected inconsistency in hash_table. Missing page %d (0x%x).\n", page, page);
 217         }
 218 
 219         pg = &page_table[page];
 220 
 221         if(!pg->count) {
 222                 printk("WARNING: %s(): trying to free an already freed page (%d)!\n", __FUNCTION__, pg->page);
 223                 return;
 224         }
 225 
 226         if(--pg->count > 0) {
 227                 return;
 228         }
 229 
 230         SAVE_FLAGS(flags); CLI();
 231 
 232         insert_on_free_list(pg);
 233 
 234         /* if page is not cached then place it at the head of the free list */
 235         if(!pg->inode) {
 236                 page_head = pg;
 237         }
 238 
 239         RESTORE_FLAGS(flags);
 240 
 241         /*
 242          * We need to wait for free pages to be greater than NR_BUF_RECLAIM,
 243          * otherwise get_free_pages() could run out of pages _again_, and it
 244          * would think that 'definitely there are no more free pages', killing
 245          * the current process prematurely.
 246          */
 247         if(kstat.free_pages > NR_BUF_RECLAIM) {
 248                 wakeup(&get_free_page);
 249         }
 250 }
 251 
 252 int is_valid_page(int page)
 253 {
 254         return (page >= 0 && page < NR_PAGES);
 255 }
 256 
 257 void update_page_cache(struct inode *i, __off_t offset, const char *buf, int count)
 258 {
 259         __off_t poffset;
 260         struct page *pg;
 261         int bytes;
 262 
 263         poffset = offset % PAGE_SIZE;
 264         offset &= PAGE_MASK;
 265         bytes = PAGE_SIZE - poffset;
 266 
 267         if(count) {
 268                 bytes = MIN(bytes, count);
 269                 if((pg = search_page_hash(i, offset))) {
 270                         page_lock(pg);
 271                         memcpy_b(pg->data + poffset, buf, bytes);
 272                         page_unlock(pg);
 273                         release_page(pg->page);
 274                 }
 275         }
 276 }
 277 
 278 int write_page(struct page *pg, struct inode *i, __off_t offset, unsigned int length)
 279 {
 280         struct fd fd_table;
 281         unsigned int size;
 282         int errno;
 283 
 284         size = MIN(i->i_size, length);
 285         fd_table.inode = i;
 286         fd_table.flags = 0;
 287         fd_table.count = 0;
 288         fd_table.offset = offset;
 289         if(i->fsop && i->fsop->write) {
 290                 errno = i->fsop->write(i, &fd_table, pg->data, size);
 291         } else {
 292                 errno = -EINVAL;
 293         }
 294 
 295         return errno;
 296 }
 297 
 298 int bread_page(struct page *pg, struct inode *i, __off_t offset, char prot, char flags)
 299 {
 300         __blk_t block;
 301         __off_t size_read;
 302         int blksize;
 303         struct buffer *buf;
 304 
 305         blksize = i->sb->s_blocksize;
 306         size_read = 0;
 307 
 308         while(size_read < PAGE_SIZE) {
 309                 if((block = bmap(i, offset + size_read, FOR_READING)) < 0) {
 310                         return 1;
 311                 }
 312                 if(block) {
 313                         if(!(buf = bread(i->dev, block, blksize))) {
 314                                 return 1;
 315                         }
 316                         memcpy_b(pg->data + size_read, buf->data, blksize);
 317                         brelse(buf);
 318                 } else {
 319                         /* fill the hole with zeros */
 320                         memset_b(pg->data + size_read, 0, blksize);
 321                 }
 322                 size_read += blksize;
 323         }
 324 
 325         /* cache any read-only or public (shared) pages */
 326         if(!(prot & PROT_WRITE) || flags & MAP_SHARED) {
 327                 pg->inode = i->inode;
 328                 pg->offset = offset;
 329                 pg->dev = i->dev;
 330                 insert_to_hash(pg);
 331         }
 332 
 333         return 0;
 334 }
 335 
 336 int file_read(struct inode *i, struct fd *fd_table, char *buffer, __size_t count)
 337 {
 338         __off_t total_read;
 339         unsigned int addr, poffset, bytes;
 340         struct page *pg;
 341 
 342         inode_lock(i);
 343 
 344         if(fd_table->offset > i->i_size) {
 345                 fd_table->offset = i->i_size;
 346         }
 347 
 348         total_read = 0;
 349 
 350         for(;;) {
 351                 count = (fd_table->offset + count > i->i_size) ? i->i_size - fd_table->offset : count;
 352                 if(!count) {
 353                         break;
 354                 }
 355 
 356                 poffset = fd_table->offset % PAGE_SIZE;
 357                 if(!(pg = search_page_hash(i, fd_table->offset & PAGE_MASK))) {
 358                         if(!(addr = kmalloc())) {
 359                                 inode_unlock(i);
 360                                 printk("%s(): returning -ENOMEM\n", __FUNCTION__);
 361                                 return -ENOMEM;
 362                         }
 363                         pg = &page_table[V2P(addr) >> PAGE_SHIFT];
 364                         if(bread_page(pg, i, fd_table->offset & PAGE_MASK, 0, MAP_SHARED)) {
 365                                 kfree(addr);
 366                                 inode_unlock(i);
 367                                 printk("%s(): returning -EIO\n", __FUNCTION__);
 368                                 return -EIO;
 369                         }
 370                 } else {
 371                         addr = (unsigned int)pg->data;
 372                 }
 373 
 374                 page_lock(pg);
 375                 bytes = PAGE_SIZE - poffset;
 376                 bytes = MIN(bytes, count);
 377                 memcpy_b(buffer + total_read, pg->data + poffset, bytes);
 378                 total_read += bytes;
 379                 count -= bytes;
 380                 fd_table->offset += bytes;
 381                 kfree(addr);
 382                 page_unlock(pg);
 383         }
 384 
 385         inode_unlock(i);
 386         return total_read;
 387 }
 388 
 389 void page_init(int pages)
 390 {
 391         struct page *pg;
 392         unsigned int n, addr;
 393 
 394         memset_b(page_table, NULL, page_table_size);
 395         memset_b(page_hash_table, NULL, page_hash_table_size);
 396 
 397         for(n = 0; n < pages; n++) {
 398                 pg = &page_table[n];
 399                 pg->page = n;
 400 
 401                 addr = n << PAGE_SHIFT;
 402                 if(addr >= KERNEL_ENTRY_ADDR && addr < V2P(_last_data_addr)) {
 403                         pg->flags = PAGE_RESERVED;
 404                         kstat.kernel_reserved++;
 405                         continue;
 406                 }
 407 
 408                 /*
 409                  * Some memory addresses are reserved, like the memory between
 410                  * 0xA0000 and 0xFFFFF and other addresses, mostly used by the
 411                  * VGA graphics adapter and BIOS.
 412                  */
 413                 if(!addr_in_bios_map(addr)) {
 414                         pg->flags = PAGE_RESERVED;
 415                         kstat.physical_reserved++;
 416                         continue;
 417                 }
 418 
 419                 pg->data = (char *)P2V(addr);
 420                 insert_on_free_list(pg);
 421         }
 422         kstat.total_mem_pages = kstat.free_pages;
 423         kstat.kernel_reserved <<= 2;
 424         kstat.physical_reserved <<= 2;
 425 }

/* [previous][next][first][last][top][bottom][index][help] */