+
+
+/* Internal use only routines */
+
+
+/*
+ * internal sub-function for address space lookup
+ * returns the target element and the address of the
+ * previous pointer The previous pointer is the address
+ * of the pointer pointing to the target element.
+ * TWS must be locked
+ */
+
+void
+tws_traverse_address_hash_list (
+ tws_hash_t tws,
+ unsigned int index,
+ vm_offset_t page_addr,
+ vm_object_t object,
+ vm_object_offset_t offset,
+ vm_map_t map,
+ tws_hash_ptr_t *target_ele,
+ tws_hash_ptr_t **previous_ptr,
+ tws_hash_ptr_t **free_list,
+ unsigned int exclusive_addr)
+{
+ int k;
+ tws_hash_ptr_t cache_ele;
+ tws_hash_ptr_t base_ele;
+
+ *target_ele = NULL;
+ *previous_ptr = NULL;
+
+ for(k=0; k<tws->expansion_count; k++) {
+ tws_hash_ele_t ele;
+ cache_ele = tws->table[k][index];
+ base_ele = cache_ele;
+ *previous_ptr = (tws_hash_ptr_t *)&(tws->table[k][index]);
+ while(cache_ele != NULL) {
+ if(((unsigned int)
+ cache_ele->element & TWS_ADDR_HASH) == 0) {
+ *previous_ptr = (tws_hash_ptr_t *)&(cache_ele->next);
+ cache_ele = cache_ele->next;
+ continue;
+ }
+ ele = (tws_hash_ele_t)((unsigned int)
+ cache_ele->element & ~TWS_ADDR_HASH);
+ if ((ele == 0) || (ele->object == 0)) {
+ /* A little clean-up of empty elements */
+ cache_ele->element = 0;
+ if(base_ele == cache_ele) {
+ base_ele = cache_ele->next;
+ tws->table[k][index] = cache_ele->next;
+ cache_ele->next = tws->free_hash_ele[k];
+ tws->free_hash_ele[k] = cache_ele;
+ cache_ele = base_ele;
+ } else {
+ **previous_ptr = cache_ele->next;
+ cache_ele->next = tws->free_hash_ele[k];
+ tws->free_hash_ele[k] = cache_ele;
+ cache_ele = **previous_ptr;
+ }
+ continue;
+ }
+
+ if ((ele->page_addr <= page_addr)
+ && (page_addr <= (ele->page_addr +
+ (vm_offset_t)TWS_INDEX_MASK))
+ && ((object == NULL)
+ || ((object == ele->object)
+ && (offset == ele->offset)
+ && (map == ele->map)))) {
+ if(exclusive_addr) {
+ int delta;
+ delta = ((page_addr - ele->page_addr)
+ >> 12);
+ if((1 << delta) & ele->page_cache) {
+ /* We've found a match */
+ *target_ele = cache_ele;
+ *free_list =
+ (tws_hash_ptr_t *)
+ &(tws->free_hash_ele[k]);
+ return;
+ }
+ } else {
+ /* We've found a match */
+ *target_ele = cache_ele;
+ *free_list = (tws_hash_ptr_t *)
+ &(tws->free_hash_ele[k]);
+ return;
+ }
+ }
+ *previous_ptr = (tws_hash_ptr_t *)&(cache_ele->next);
+ cache_ele = cache_ele->next;
+ }
+ }
+}
+
+
+/*
+ * internal sub-function for object space lookup
+ * returns the target element and the address of the
+ * previous pointer The previous pointer is the address
+ * of the pointer pointing to the target element.
+ * TWS must be locked
+ */
+
+
+void
+tws_traverse_object_hash_list (
+ tws_hash_t tws,
+ unsigned int index,
+ vm_object_t object,
+ vm_object_offset_t offset,
+ unsigned int page_mask,
+ tws_hash_ptr_t *target_ele,
+ tws_hash_ptr_t **previous_ptr,
+ tws_hash_ptr_t **free_list)
+{
+ int k;
+ tws_hash_ptr_t cache_ele;
+ tws_hash_ptr_t base_ele;
+
+ *target_ele = NULL;
+ *previous_ptr = NULL;
+
+ for(k=0; k<tws->expansion_count; k++) {
+ cache_ele = tws->table[k][index];
+ base_ele = cache_ele;
+ *previous_ptr = &(tws->table[k][index]);
+ while(cache_ele != NULL) {
+ if((((unsigned int)cache_ele->element)
+ & TWS_ADDR_HASH) != 0) {
+ *previous_ptr = &(cache_ele->next);
+ cache_ele = cache_ele->next;
+ continue;
+ }
+ if ((cache_ele->element == 0) ||
+ (cache_ele->element->object == 0)) {
+ /* A little clean-up of empty elements */
+ cache_ele->element = 0;
+ if(base_ele == cache_ele) {
+ base_ele = cache_ele->next;
+ tws->table[k][index] = cache_ele->next;
+ cache_ele->next = tws->free_hash_ele[k];
+ tws->free_hash_ele[k] = cache_ele;
+ cache_ele = tws->table[k][index];
+ } else {
+ **previous_ptr = cache_ele->next;
+ cache_ele->next = tws->free_hash_ele[k];
+ tws->free_hash_ele[k] = cache_ele;
+ cache_ele = **previous_ptr;
+ }
+ continue;
+ }
+ if ((cache_ele->element->object == object)
+ && (cache_ele->element->offset ==
+ (offset - (offset & ~TWS_HASH_OFF_MASK)))) {
+ if((cache_ele->element->page_cache & page_mask)
+ || (page_mask == 0xFFFFFFFF)) {
+ /* We've found a match */
+ *target_ele = cache_ele;
+ *free_list = &(tws->free_hash_ele[k]);
+ return;
+ }
+ }
+ *previous_ptr = (tws_hash_ptr_t *)&(cache_ele->next);
+ cache_ele = cache_ele->next;
+ }
+ }
+}
+
+
+/*
+ * For a given object/offset, discover whether the indexed 32 page frame
+ * containing the object/offset exists and if their are at least threshold
+ * pages present. Returns true if population meets threshold.
+ */
+int
+tws_test_for_community(
+ tws_hash_t tws,
+ vm_object_t object,
+ vm_object_offset_t offset,
+ unsigned int threshold,
+ unsigned int *page_mask)
+{
+ int index;
+ tws_hash_ptr_t cache_ele;
+ tws_hash_ptr_t *trailer;
+ tws_hash_ptr_t *free_list;
+ int community = 0;
+
+ index = do_tws_hash(object, offset,
+ tws->number_of_elements, tws->number_of_lines);
+ tws_traverse_object_hash_list(tws, index, object, offset, 0xFFFFFFFF,
+ &cache_ele, &trailer, &free_list);
+
+ if(cache_ele != NULL) {
+ int i;
+ int ctr;
+ ctr = 0;
+ for(i=1; i!=0; i=i<<1) {
+ if(i & cache_ele->element->page_cache)
+ ctr++;
+ if(ctr == threshold) {
+ community = 1;
+ *page_mask = cache_ele->element->page_cache;
+ break;
+ }
+ }
+ }
+
+ return community;
+
+}
+
+
+/*
+ * Gets new hash element for object hash from free pools
+ * TWS must be locked
+ */
+
+tws_hash_ptr_t
+new_obj_hash(
+ tws_hash_t tws,
+ unsigned int set,
+ unsigned int index)
+{
+ tws_hash_ptr_t element;
+
+ if(tws->obj_free_count[set] < tws->number_of_lines * tws->number_of_elements) {
+ element = &(tws->table_ele[set][tws->obj_free_count[set]]);
+ tws->obj_free_count[set]+=1;
+ } else if(tws->free_hash_ele[set] == NULL) {
+ return NULL;
+ } else {
+ element = tws->free_hash_ele[set];
+ if(element == NULL)
+ return element;
+ tws->free_hash_ele[set] = tws->free_hash_ele[set]->next;
+ }
+ element->element = 0;
+ element->next = tws->table[set][index];
+ tws->table[set][index] = element;
+ return element;
+}
+
+/*
+ * Gets new hash element for addr hash from free pools
+ * TWS must be locked
+ */
+
+tws_hash_ptr_t
+new_addr_hash(
+ tws_hash_t tws,
+ unsigned int set,
+ unsigned int index)
+{
+ tws_hash_ptr_t element;
+
+ if(tws->addr_free_count[set]
+ < tws->number_of_lines * tws->number_of_elements) {
+ element = &(tws->alt_ele[set][tws->addr_free_count[set]]);
+ tws->addr_free_count[set]+=1;
+ } else if(tws->free_hash_ele[set] == NULL) {
+ return NULL;
+ } else {
+ element = tws->free_hash_ele[set];
+ if(element == NULL)
+ return element;
+ tws->free_hash_ele[set] = tws->free_hash_ele[set]->next;
+ }
+ element->element = (tws_hash_ele_t)TWS_ADDR_HASH;
+ element->next = tws->table[set][index];
+ tws->table[set][index] = element;
+ return element;
+}
projects / apple / xnu.git / blobdiff