133c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris/* 233c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris * Copyright (C) 2015 The Android Open Source Project 333c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris * 433c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris * Licensed under the Apache License, Version 2.0 (the "License"); 533c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris * you may not use this file except in compliance with the License. 633c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris * You may obtain a copy of the License at 733c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris * 833c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris * http://www.apache.org/licenses/LICENSE-2.0 933c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris * 1033c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris * Unless required by applicable law or agreed to in writing, software 1133c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris * distributed under the License is distributed on an "AS IS" BASIS, 1233c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1333c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris * See the License for the specific language governing permissions and 1433c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris * limitations under the License. 1533c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris */ 1633c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris 1733c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris#include <err.h> 1833c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris#include <inttypes.h> 1933c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris#include <stdatomic.h> 2033c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris#include <stdio.h> 2133c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris#include <stdlib.h> 2233c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris#include <string.h> 2333c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris#include <sys/mman.h> 2433c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris#include <unistd.h> 2533c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris 2633c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris#include "err.h" 2733c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris#include "Pointers.h" 2833c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris 2933c03d38298ff359d8829aea91bb02b26caab245Christopher FerrisPointers::Pointers(size_t max_allocs) { 3033c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris size_t pagesize = getpagesize(); 3133c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris // Create a mmap that contains a 4:1 ratio of allocations to entries. 3233c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris // Align to a page. 3333c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris pointers_size_ = (max_allocs * 4 * sizeof(pointer_data) + pagesize - 1) & ~(pagesize - 1); 3433c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris max_pointers_ = pointers_size_ / sizeof(pointer_data); 3533c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris void* memory = mmap(nullptr, pointers_size_, PROT_READ | PROT_WRITE, 3633c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris MAP_ANON | MAP_PRIVATE, -1, 0); 3733c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris if (memory == MAP_FAILED) { 3833c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris err(1, "Unable to allocate data for pointer hash: %zu total_allocs\n", max_allocs); 3933c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris } 4033c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris // Make sure that all of the PSS for this is counted right away. 4133c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris memset(memory, 0, pointers_size_); 4233c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris pointers_ = reinterpret_cast<pointer_data*>(memory); 4333c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris} 4433c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris 4533c03d38298ff359d8829aea91bb02b26caab245Christopher FerrisPointers::~Pointers() { 4633c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris if (pointers_ != nullptr) { 4733c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris munmap(pointers_, pointers_size_); 4833c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris pointers_ = nullptr; 4933c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris } 5033c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris} 5133c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris 5233c03d38298ff359d8829aea91bb02b26caab245Christopher Ferrisvoid Pointers::Add(uintptr_t key_pointer, void* pointer) { 5333c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris pointer_data* data = FindEmpty(key_pointer); 5433c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris if (data == nullptr) { 5533c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris err(1, "No empty entry found for 0x%" PRIxPTR "\n", key_pointer); 5633c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris } 5733c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris atomic_store(&data->key_pointer, key_pointer); 5833c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris data->pointer = pointer; 5933c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris} 6033c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris 6133c03d38298ff359d8829aea91bb02b26caab245Christopher Ferrisvoid* Pointers::Remove(uintptr_t key_pointer) { 6233c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris if (key_pointer == 0) { 6333c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris err(1, "Illegal zero value passed to Remove\n"); 6433c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris } 6533c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris 6633c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris pointer_data* data = Find(key_pointer); 6733c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris if (data == nullptr) { 6833c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris err(1, "No pointer value found for 0x%" PRIxPTR "\n", key_pointer); 6933c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris } 7033c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris 7133c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris void* pointer = data->pointer; 7233c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris atomic_store(&data->key_pointer, uintptr_t(0)); 7333c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris 7433c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris return pointer; 7533c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris} 7633c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris 7733c03d38298ff359d8829aea91bb02b26caab245Christopher Ferrispointer_data* Pointers::Find(uintptr_t key_pointer) { 7833c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris size_t index = GetHash(key_pointer); 7933c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris for (size_t entries = max_pointers_; entries != 0; entries--) { 8033c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris if (atomic_load(&pointers_[index].key_pointer) == key_pointer) { 8133c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris return pointers_ + index; 8233c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris } 8333c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris if (++index == max_pointers_) { 8433c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris index = 0; 8533c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris } 8633c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris } 8733c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris return nullptr; 8833c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris} 8933c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris 9033c03d38298ff359d8829aea91bb02b26caab245Christopher Ferrispointer_data* Pointers::FindEmpty(uintptr_t key_pointer) { 9133c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris size_t index = GetHash(key_pointer); 9233c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris for (size_t entries = 0; entries < max_pointers_; entries++) { 9333c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris uintptr_t empty = 0; 9433c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris if (atomic_compare_exchange_strong(&pointers_[index].key_pointer, &empty, 9533c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris uintptr_t(1))) { 9633c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris return pointers_ + index; 9733c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris } 9833c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris if (++index == max_pointers_) { 9933c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris index = 0; 10033c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris } 10133c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris } 10233c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris return nullptr; 10333c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris} 10433c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris 10533c03d38298ff359d8829aea91bb02b26caab245Christopher Ferrissize_t Pointers::GetHash(uintptr_t key_pointer) { 10633c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris return key_pointer % max_pointers_; 10733c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris} 10833c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris 10933c03d38298ff359d8829aea91bb02b26caab245Christopher Ferrisvoid Pointers::FreeAll() { 11033c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris for (size_t i = 0; i < max_pointers_; i++) { 11133c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris if (atomic_load(&pointers_[i].key_pointer) != 0) { 11233c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris free(pointers_[i].pointer); 11333c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris } 11433c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris } 11533c03d38298ff359d8829aea91bb02b26caab245Christopher Ferris} 116