Subversion Repositories HelenOS-historic

Rev

Rev 1380 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * Copyright (C) 2006 Jakub Jermar
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  *
  9.  * - Redistributions of source code must retain the above copyright
  10.  *   notice, this list of conditions and the following disclaimer.
  11.  * - Redistributions in binary form must reproduce the above copyright
  12.  *   notice, this list of conditions and the following disclaimer in the
  13.  *   documentation and/or other materials provided with the distribution.
  14.  * - The name of the author may not be used to endorse or promote products
  15.  *   derived from this software without specific prior written permission.
  16.  *
  17.  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18.  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19.  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20.  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21.  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22.  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23.  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24.  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25.  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26.  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27.  */
  28.  
  29. /**
  30.  * @file    page_ht.c
  31.  * @brief   Virtual Address Translation (VAT) for global page hash table.
  32.  */
  33.  
  34. #include <genarch/mm/page_ht.h>
  35. #include <mm/page.h>
  36. #include <arch/mm/page.h>
  37. #include <mm/frame.h>
  38. #include <mm/slab.h>
  39. #include <mm/as.h>
  40. #include <arch/mm/asid.h>
  41. #include <arch/types.h>
  42. #include <typedefs.h>
  43. #include <arch/asm.h>
  44. #include <synch/spinlock.h>
  45. #include <arch.h>
  46. #include <debug.h>
  47. #include <memstr.h>
  48. #include <adt/hash_table.h>
  49. #include <align.h>
  50.  
  51. static index_t hash(__native key[]);
  52. static bool compare(__native key[], count_t keys, link_t *item);
  53. static void remove_callback(link_t *item);
  54.  
  55. static void ht_mapping_insert(as_t *as, __address page, __address frame, int flags);
  56. static void ht_mapping_remove(as_t *as, __address page);
  57. static pte_t *ht_mapping_find(as_t *as, __address page);
  58.  
  59. /**
  60.  * This lock protects the page hash table. It must be acquired
  61.  * after address space lock and after any address space area
  62.  * locks.
  63.  */
  64. mutex_t page_ht_lock;
  65.  
  66. /**
  67.  * Page hash table.
  68.  * The page hash table may be accessed only when page_ht_lock is held.
  69.  */
  70. hash_table_t page_ht;
  71.  
  72. /** Hash table operations for page hash table. */
  73. hash_table_operations_t ht_operations = {
  74.     .hash = hash,
  75.     .compare = compare,
  76.     .remove_callback = remove_callback
  77. };
  78.  
  79. /** Page mapping operations for page hash table architectures. */
  80. page_mapping_operations_t ht_mapping_operations = {
  81.     .mapping_insert = ht_mapping_insert,
  82.     .mapping_remove = ht_mapping_remove,
  83.     .mapping_find = ht_mapping_find
  84. };
  85.  
  86. /** Compute page hash table index.
  87.  *
  88.  * @param key Array of two keys (i.e. page and address space).
  89.  *
  90.  * @return Index into page hash table.
  91.  */
  92. index_t hash(__native key[])
  93. {
  94.     as_t *as = (as_t *) key[KEY_AS];
  95.     __address page = (__address) key[KEY_PAGE];
  96.     index_t index;
  97.    
  98.     /*
  99.      * Virtual page addresses have roughly the same probability
  100.      * of occurring. Least significant bits of VPN compose the
  101.      * hash index.
  102.      */
  103.     index = ((page >> PAGE_WIDTH) & (PAGE_HT_ENTRIES-1));
  104.    
  105.     /*
  106.      * Address space structures are likely to be allocated from
  107.      * similar addresses. Least significant bits compose the
  108.      * hash index.
  109.      */
  110.     index |= ((__native) as) & (PAGE_HT_ENTRIES-1);
  111.    
  112.     return index;
  113. }
  114.  
  115. /** Compare page hash table item with page and/or address space.
  116.  *
  117.  * @param key Array of one or two keys (i.e. page and/or address space).
  118.  * @param keys Number of keys passed.
  119.  * @param item Item to compare the keys with.
  120.  *
  121.  * @return true on match, false otherwise.
  122.  */
  123. bool compare(__native key[], count_t keys, link_t *item)
  124. {
  125.     pte_t *t;
  126.  
  127.     ASSERT(item);
  128.     ASSERT((keys > 0) && (keys <= PAGE_HT_KEYS));
  129.  
  130.     /*
  131.      * Convert item to PTE.
  132.      */
  133.     t = hash_table_get_instance(item, pte_t, link);
  134.  
  135.     if (keys == PAGE_HT_KEYS) {
  136.         return (key[KEY_AS] == (__address) t->as) && (key[KEY_PAGE] == t->page);
  137.     } else {
  138.         return (key[KEY_AS] == (__address) t->as);
  139.     }
  140. }
  141.  
  142. /** Callback on page hash table item removal.
  143.  *
  144.  * @param item Page hash table item being removed.
  145.  */
  146. void remove_callback(link_t *item)
  147. {
  148.     pte_t *t;
  149.  
  150.     ASSERT(item);
  151.  
  152.     /*
  153.      * Convert item to PTE.
  154.      */
  155.     t = hash_table_get_instance(item, pte_t, link);
  156.  
  157.     free(t);
  158. }
  159.  
  160. /** Map page to frame using page hash table.
  161.  *
  162.  * Map virtual address page to physical address frame
  163.  * using flags.
  164.  *
  165.  * The page table must be locked and interrupts must be disabled.
  166.  *
  167.  * @param as Address space to which page belongs.
  168.  * @param page Virtual address of the page to be mapped.
  169.  * @param frame Physical address of memory frame to which the mapping is done.
  170.  * @param flags Flags to be used for mapping.
  171.  */
  172. void ht_mapping_insert(as_t *as, __address page, __address frame, int flags)
  173. {
  174.     pte_t *t;
  175.     __native key[2] = { (__address) as, page = ALIGN_DOWN(page, PAGE_SIZE) };
  176.    
  177.     if (!hash_table_find(&page_ht, key)) {
  178.         t = (pte_t *) malloc(sizeof(pte_t), FRAME_ATOMIC);
  179.         ASSERT(t != NULL);
  180.  
  181.         t->g = (flags & PAGE_GLOBAL) != 0;
  182.         t->x = (flags & PAGE_EXEC) != 0;
  183.         t->w = (flags & PAGE_WRITE) != 0;
  184.         t->k = !(flags & PAGE_USER);
  185.         t->c = (flags & PAGE_CACHEABLE) != 0;
  186.         t->p = !(flags & PAGE_NOT_PRESENT);
  187.  
  188.         t->as = as;
  189.         t->page = ALIGN_DOWN(page, PAGE_SIZE);
  190.         t->frame = ALIGN_DOWN(frame, FRAME_SIZE);
  191.  
  192.         hash_table_insert(&page_ht, key, &t->link);
  193.     }
  194. }
  195.  
  196. /** Remove mapping of page from page hash table.
  197.  *
  198.  * Remove any mapping of page within address space as.
  199.  * TLB shootdown should follow in order to make effects of
  200.  * this call visible.
  201.  *
  202.  * The page table must be locked and interrupts must be disabled.
  203.  *
  204.  * @param as Address space to wich page belongs.
  205.  * @param page Virtual address of the page to be demapped.
  206.  */
  207. void ht_mapping_remove(as_t *as, __address page)
  208. {
  209.     __native key[2] = { (__address) as, page = ALIGN_DOWN(page, PAGE_SIZE) };
  210.    
  211.     /*
  212.      * Note that removed PTE's will be freed
  213.      * by remove_callback().
  214.      */
  215.     hash_table_remove(&page_ht, key, 2);
  216. }
  217.  
  218.  
  219. /** Find mapping for virtual page in page hash table.
  220.  *
  221.  * Find mapping for virtual page.
  222.  *
  223.  * The page table must be locked and interrupts must be disabled.
  224.  *
  225.  * @param as Address space to wich page belongs.
  226.  * @param page Virtual page.
  227.  *
  228.  * @return NULL if there is no such mapping; requested mapping otherwise.
  229.  */
  230. pte_t *ht_mapping_find(as_t *as, __address page)
  231. {
  232.     link_t *hlp;
  233.     pte_t *t = NULL;
  234.     __native key[2] = { (__address) as, page = ALIGN_DOWN(page, PAGE_SIZE) };
  235.    
  236.     hlp = hash_table_find(&page_ht, key);
  237.     if (hlp)
  238.         t = hash_table_get_instance(hlp, pte_t, link);
  239.  
  240.     return t;
  241. }
  242.