Welcome to The Fiwix Project
A UNIX-like kernel for the i386 architecture
![[previous]](../icons/n_left.png){kind=icon}
![[next]](../icons/n_right.png){kind=icon}
![[first]](../icons/first.png){kind=icon}
![[last]](../icons/last.png){kind=icon}
![[top]](../icons/n_top.png){kind=icon}
![[bottom]](../icons/bottom.png){kind=icon}
![[index]](../icons/index.png){kind=icon}
![[help]](../icons/help.png){kind=icon}
*/
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 }
![[top]](../icons/top.png){kind=icon}
![[bottom]](../icons/n_bottom.png){kind=icon}
*/
