Diff
Modified: trunk/Source/bmalloc/libpas/Documentation.md (294865 => 294866)
--- trunk/Source/bmalloc/libpas/Documentation.md 2022-05-26 03:39:27 UTC (rev 294865)
+++ trunk/Source/bmalloc/libpas/Documentation.md 2022-05-26 03:46:27 UTC (rev 294866)
@@ -1178,7 +1178,8 @@
.medium_bitfit_min_align_shift = PAS_MIN_MEDIUM_ALIGN_SHIFT, \
.use_marge_bitfit = true, \
.marge_bitfit_min_align_shift = PAS_MIN_MARGE_ALIGN_SHIFT, \
- .marge_bitfit_page_size = PAS_MARGE_PAGE_DEFAULT_SIZE)
+ .marge_bitfit_page_size = PAS_MARGE_PAGE_DEFAULT_SIZE, \
+ .pgm_enabled = false)
PAS_API extern pas_heap_config iso_heap_config;
@@ -1236,6 +1237,28 @@
medium or marge. So, the JIT heap config focuses on just using bitfit and large and it forces bitfit to use
page header tables even for the small bitfit page config.
+## Security Considerations
+
+### Probabilistic Guard Malloc
+
+ Probabilistic Guard Malloc (PGM) is a new allocator designed to catch use after free attempts and out of bounds accesses.
+ It behaves similarly to AddressSanitizer (ASAN), but aims to have minimal runtime overhead.
+
+ The design of PGM is quite simple. Each time an allocation is performed an additional guard page is added above and below the newly
+ allocated page(s). An allocation may span multiple pages. When a deallocation is performed, the page(s) allocated will be protected
+ using mprotect to ensure that any use after frees will trigger a crash. Virtual memory addresses are never reused, so we will never run
+ into a case where object 1 is freed, object 2 is allocated over the same address space, and object 1 then accesses the memory address
+ space of now object 2.
+
+ PGM does add notable memory overhead. Each allocation, no matter the size, adds an additional 2 guard pages (8KB for X86_64 and 32KB
+ for ARM64). In addition, there may be free memory left over in the page(s) allocated for the user. This memory may not be used by any
+ other allocation.
+
+ We added limits on virtual memory and wasted memory to help limit the memory impact on the overall system. Virtual memory for this
+ allocator is limited to 1GB. Wasted memory, which is the unused memory in the page(s) allocated by the user, is limited to 1MB.
+ These overall limits should ensure that the memory impact on the system is minimal, while helping to tackle the problems of catching
+ use after frees and out of bounds accesses.
+
## The Fast Paths
All of the discussion in the previous sections is about the innards of libpas. But ultimately, clients want to
Modified: trunk/Source/bmalloc/libpas/ReadMe.md (294865 => 294866)
--- trunk/Source/bmalloc/libpas/ReadMe.md 2022-05-26 03:39:27 UTC (rev 294865)
+++ trunk/Source/bmalloc/libpas/ReadMe.md 2022-05-26 03:46:27 UTC (rev 294866)
@@ -1,9 +1,9 @@
# libpas - Phil's Awesome System
Libpas is a configurable memory allocator toolkit designed to enable adoption
-of isoheaps. Currently, libpas's main client is WebKit's bmalloc project, where
+of isoheaps. Currently, libpas' main client is WebKit's bmalloc project, where
it's used as a replacement for all of bmalloc's functionality (bmalloc::api,
-IsoHeap<>, and Gigacage). Libpas's jit_heap API is also used by WebKit's
+IsoHeap<>, and Gigacage). Libpas' jit_heap API is also used by WebKit's
ExecutableAllocator.
@@ -10,11 +10,11 @@
# How To Build And Test
This section describes how to build libpas standalone. You'll be doing this a
-lot when making changes to libpas. It's wise to run libpas's tests before
+lot when making changes to libpas. It's wise to run libpas' tests before
trying out your change in any larger system (like WebKit) since libpas tests
are great at catching bugs. If libpas passes its own tests then basic browsing
will seem to work. In production, libpas gets built as part of some other
-project (like bmalloc), which just pulls all of libpas's files into that
+project (like bmalloc), which just pulls all of libpas' files into that
project's build system.
Build and test:
@@ -64,7 +64,7 @@
project; for example, when libpas sees the PAS_BMALLOC macro, it will provide
everything that WebKit's bmalloc library needs to create an allocator.
-Libpas's toolkit of allocators has three building blocks:
+Libpas' toolkit of allocators has three building blocks:
- The segregated heap. This implements something like simple segregated
storage. Roughly speaking, size classes hold onto collections of pages, and
@@ -99,7 +99,7 @@
All of the heaps are able to participate in physical page sharing. This means
that anytime any system page of memory managed by the heap becomes totally
-empty, it becomes eligible for being returned to the OS via decommit. Libpas's
+empty, it becomes eligible for being returned to the OS via decommit. Libpas'
decommit strategy is particularly well tuned so as to compensate for the
inherent memory overheads of isoheaping. Libpas achieves much better memory
usage than bmalloc because it returns pages sooner than bmalloc would have, and
@@ -109,7 +109,7 @@
Libpas is a heavy user of fine-grained locking and intricate lock dancing. Some
data structures will be protected by any of a collection of different locks,
and lock acquisition involves getting the lock, checking if you got the right
-lock, and possibly relooping. Libpas's algorithms are designed around:
+lock, and possibly relooping. Libpas' algorithms are designed around:
- Reducing the likelihood that any long-running operation would want to hold a
lock that any frequently-running operation would ever need. For example,
Modified: trunk/Source/bmalloc/libpas/src/libpas/bmalloc_heap_config.h (294865 => 294866)
--- trunk/Source/bmalloc/libpas/src/libpas/bmalloc_heap_config.h 2022-05-26 03:39:27 UTC (rev 294865)
+++ trunk/Source/bmalloc/libpas/src/libpas/bmalloc_heap_config.h 2022-05-26 03:46:27 UTC (rev 294866)
@@ -74,7 +74,8 @@
.medium_bitfit_min_align_shift = PAS_MIN_MEDIUM_ALIGN_SHIFT, \
.use_marge_bitfit = true, \
.marge_bitfit_min_align_shift = PAS_MIN_MARGE_ALIGN_SHIFT, \
- .marge_bitfit_page_size = PAS_MARGE_PAGE_DEFAULT_SIZE)
+ .marge_bitfit_page_size = PAS_MARGE_PAGE_DEFAULT_SIZE, \
+ .pgm_enabled = false)
PAS_API extern pas_heap_config bmalloc_heap_config;
Modified: trunk/Source/bmalloc/libpas/src/libpas/hotbit_heap_config.h (294865 => 294866)
--- trunk/Source/bmalloc/libpas/src/libpas/hotbit_heap_config.h 2022-05-26 03:39:27 UTC (rev 294865)
+++ trunk/Source/bmalloc/libpas/src/libpas/hotbit_heap_config.h 2022-05-26 03:46:27 UTC (rev 294866)
@@ -75,7 +75,8 @@
.medium_bitfit_min_align_shift = PAS_MIN_MEDIUM_ALIGN_SHIFT, \
.use_marge_bitfit = true, \
.marge_bitfit_min_align_shift = PAS_MIN_MARGE_ALIGN_SHIFT, \
- .marge_bitfit_page_size = PAS_MARGE_PAGE_DEFAULT_SIZE)
+ .marge_bitfit_page_size = PAS_MARGE_PAGE_DEFAULT_SIZE, \
+ .pgm_enabled = false)
PAS_API extern pas_heap_config hotbit_heap_config;
Modified: trunk/Source/bmalloc/libpas/src/libpas/iso_heap_config.h (294865 => 294866)
--- trunk/Source/bmalloc/libpas/src/libpas/iso_heap_config.h 2022-05-26 03:39:27 UTC (rev 294865)
+++ trunk/Source/bmalloc/libpas/src/libpas/iso_heap_config.h 2022-05-26 03:46:27 UTC (rev 294866)
@@ -73,7 +73,8 @@
.medium_bitfit_min_align_shift = PAS_MIN_MEDIUM_ALIGN_SHIFT, \
.use_marge_bitfit = true, \
.marge_bitfit_min_align_shift = PAS_MIN_MARGE_ALIGN_SHIFT, \
- .marge_bitfit_page_size = PAS_MARGE_PAGE_DEFAULT_SIZE)
+ .marge_bitfit_page_size = PAS_MARGE_PAGE_DEFAULT_SIZE, \
+ .pgm_enabled = false)
PAS_API extern pas_heap_config iso_heap_config;
Modified: trunk/Source/bmalloc/libpas/src/libpas/iso_test_heap_config.h (294865 => 294866)
--- trunk/Source/bmalloc/libpas/src/libpas/iso_test_heap_config.h 2022-05-26 03:39:27 UTC (rev 294865)
+++ trunk/Source/bmalloc/libpas/src/libpas/iso_test_heap_config.h 2022-05-26 03:46:27 UTC (rev 294866)
@@ -73,7 +73,8 @@
.medium_bitfit_min_align_shift = PAS_MIN_MEDIUM_ALIGN_SHIFT, \
.use_marge_bitfit = true, \
.marge_bitfit_min_align_shift = PAS_MIN_MARGE_ALIGN_SHIFT, \
- .marge_bitfit_page_size = PAS_MARGE_PAGE_DEFAULT_SIZE)
+ .marge_bitfit_page_size = PAS_MARGE_PAGE_DEFAULT_SIZE, \
+ .pgm_enabled = false)
PAS_API extern pas_heap_config iso_test_heap_config;
Modified: trunk/Source/bmalloc/libpas/src/libpas/minalign32_heap_config.h (294865 => 294866)
--- trunk/Source/bmalloc/libpas/src/libpas/minalign32_heap_config.h 2022-05-26 03:39:27 UTC (rev 294865)
+++ trunk/Source/bmalloc/libpas/src/libpas/minalign32_heap_config.h 2022-05-26 03:46:27 UTC (rev 294866)
@@ -77,7 +77,8 @@
.medium_bitfit_min_align_shift = PAS_MIN_MEDIUM_ALIGN_SHIFT, \
.use_marge_bitfit = true, \
.marge_bitfit_min_align_shift = PAS_MIN_MARGE_ALIGN_SHIFT, \
- .marge_bitfit_page_size = PAS_MARGE_PAGE_DEFAULT_SIZE)
+ .marge_bitfit_page_size = PAS_MARGE_PAGE_DEFAULT_SIZE, \
+ .pgm_enabled = false)
PAS_API extern pas_heap_config minalign32_heap_config;
Modified: trunk/Source/bmalloc/libpas/src/libpas/pagesize64k_heap_config.h (294865 => 294866)
--- trunk/Source/bmalloc/libpas/src/libpas/pagesize64k_heap_config.h 2022-05-26 03:39:27 UTC (rev 294865)
+++ trunk/Source/bmalloc/libpas/src/libpas/pagesize64k_heap_config.h 2022-05-26 03:46:27 UTC (rev 294866)
@@ -76,7 +76,8 @@
.medium_shared_segregated_logging_mode = pas_segregated_deallocation_size_aware_logging_mode, \
.use_medium_bitfit = true, \
.medium_bitfit_min_align_shift = PAS_MIN_MEDIUM_ALIGN_SHIFT, \
- .use_marge_bitfit = false)
+ .use_marge_bitfit = false, \
+ .pgm_enabled = false)
PAS_API extern pas_heap_config pagesize64k_heap_config;
Modified: trunk/Source/bmalloc/libpas/src/libpas/pas_baseline_allocator_table.c (294865 => 294866)
--- trunk/Source/bmalloc/libpas/src/libpas/pas_baseline_allocator_table.c 2022-05-26 03:39:27 UTC (rev 294865)
+++ trunk/Source/bmalloc/libpas/src/libpas/pas_baseline_allocator_table.c 2022-05-26 03:46:27 UTC (rev 294866)
@@ -63,8 +63,7 @@
unsigned pas_baseline_allocator_table_get_random_index(void)
{
- return pas_get_random(pas_fast_random, PAS_MIN(PAS_NUM_BASELINE_ALLOCATORS,
- pas_baseline_allocator_table_bound));
+ return pas_get_fast_random(PAS_MIN(PAS_NUM_BASELINE_ALLOCATORS, pas_baseline_allocator_table_bound));
}
bool pas_baseline_allocator_table_for_all(pas_allocator_scavenge_action action)
Modified: trunk/Source/bmalloc/libpas/src/libpas/pas_dynamic_primitive_heap_map.c (294865 => 294866)
--- trunk/Source/bmalloc/libpas/src/libpas/pas_dynamic_primitive_heap_map.c 2022-05-26 03:39:27 UTC (rev 294865)
+++ trunk/Source/bmalloc/libpas/src/libpas/pas_dynamic_primitive_heap_map.c 2022-05-26 03:46:27 UTC (rev 294866)
@@ -87,13 +87,13 @@
being dynamically changed. We try to allow that. */
result = heaps_for_size->heaps[
- pas_get_random(pas_fast_random, heaps_for_size->num_heaps)];
+ pas_get_fast_random(heaps_for_size->num_heaps)];
} else {
if (map->num_heaps >= map->max_heaps) {
if (verbose)
pas_log("Returning existing heap globally.\n");
- result = map->heaps[pas_get_random(pas_fast_random, map->num_heaps)];
+ result = map->heaps[pas_get_fast_random(map->num_heaps)];
} else {
pas_simple_type_with_key_data* key_data;
Modified: trunk/Source/bmalloc/libpas/src/libpas/pas_heap_config.h (294865 => 294866)
--- trunk/Source/bmalloc/libpas/src/libpas/pas_heap_config.h 2022-05-26 03:39:27 UTC (rev 294865)
+++ trunk/Source/bmalloc/libpas/src/libpas/pas_heap_config.h 2022-05-26 03:46:27 UTC (rev 294866)
@@ -174,6 +174,9 @@
bool aligned_allocator_talks_to_sharing_pool;
pas_deallocator deallocator;
+ /* Configure whether probabilistic guard malloc may be called or not during allocation. */
+ bool pgm_enabled;
+
/* Tells if it's OK to call mmap on memory managed by this heap. */
pas_mmap_capability mmap_capability;
Modified: trunk/Source/bmalloc/libpas/src/libpas/pas_heap_config_utils.h (294865 => 294866)
--- trunk/Source/bmalloc/libpas/src/libpas/pas_heap_config_utils.h 2022-05-26 03:39:27 UTC (rev 294865)
+++ trunk/Source/bmalloc/libpas/src/libpas/pas_heap_config_utils.h 2022-05-26 03:46:27 UTC (rev 294866)
@@ -92,6 +92,7 @@
bool use_marge_bitfit;
uint8_t marge_bitfit_min_align_shift;
size_t marge_bitfit_page_size;
+ bool pgm_enabled;
} pas_basic_heap_config_arguments;
#define PAS_BASIC_HEAP_CONFIG_SEGREGATED_HEAP_FIELDS(name, ...) \
@@ -340,7 +341,8 @@
.for_each_shared_page_directory_remote = \
pas_heap_config_utils_for_each_shared_page_directory_remote, \
.dump_shared_page_directory_arg = pas_shared_page_directory_by_size_dump_directory_arg, \
- PAS_HEAP_CONFIG_SPECIALIZATIONS(name ## _heap_config) \
+ PAS_HEAP_CONFIG_SPECIALIZATIONS(name ## _heap_config), \
+ .pgm_enabled = false \
})
#define PAS_BASIC_HEAP_CONFIG_SEGREGATED_HEAP_DECLARATIONS(name, upcase_name) \
Modified: trunk/Source/bmalloc/libpas/src/libpas/pas_large_heap.c (294865 => 294866)
--- trunk/Source/bmalloc/libpas/src/libpas/pas_large_heap.c 2022-05-26 03:39:27 UTC (rev 294865)
+++ trunk/Source/bmalloc/libpas/src/libpas/pas_large_heap.c 2022-05-26 03:46:27 UTC (rev 294866)
@@ -38,6 +38,7 @@
#include "pas_large_sharing_pool.h"
#include "pas_large_map.h"
#include "pas_page_malloc.h"
+#include "pas_probabilistic_guard_malloc_allocator.h"
#include <stdio.h>
void pas_large_heap_construct(pas_large_heap* heap)
@@ -184,6 +185,24 @@
return result;
}
+pas_allocation_result
+pas_large_heap_try_allocate_pgm(pas_large_heap* heap,
+ size_t size,
+ size_t alignment,
+ pas_heap_config* heap_config,
+ pas_physical_memory_transaction* transaction)
+{
+ pas_allocation_result result;
+ result = pas_probabilistic_guard_malloc_allocate(heap, size, heap_config, transaction);
+
+ /* PGM may not succeed for a variety of reasons. We will give it a last ditch effort to try to do a
+ regular allocation instead. */
+ if (!result.did_succeed)
+ result = pas_large_heap_try_allocate(heap, size, alignment, heap_config, transaction);
+
+ return result;
+}
+
bool pas_large_heap_try_deallocate(uintptr_t begin,
pas_heap_config* heap_config)
{
Modified: trunk/Source/bmalloc/libpas/src/libpas/pas_large_heap.h (294865 => 294866)
--- trunk/Source/bmalloc/libpas/src/libpas/pas_large_heap.h 2022-05-26 03:39:27 UTC (rev 294865)
+++ trunk/Source/bmalloc/libpas/src/libpas/pas_large_heap.h 2022-05-26 03:46:27 UTC (rev 294866)
@@ -62,6 +62,12 @@
pas_heap_config* config,
pas_physical_memory_transaction* transaction);
+PAS_API pas_allocation_result
+pas_large_heap_try_allocate_pgm(pas_large_heap* heap,
+ size_t size, size_t alignment,
+ pas_heap_config* config,
+ pas_physical_memory_transaction* transaction);
+
/* Returns true if an object was found and deallocated. */
PAS_API bool pas_large_heap_try_deallocate(uintptr_t base,
pas_heap_config* config);
Modified: trunk/Source/bmalloc/libpas/src/libpas/pas_probabilistic_guard_malloc_allocator.c (294865 => 294866)
--- trunk/Source/bmalloc/libpas/src/libpas/pas_probabilistic_guard_malloc_allocator.c 2022-05-26 03:39:27 UTC (rev 294865)
+++ trunk/Source/bmalloc/libpas/src/libpas/pas_probabilistic_guard_malloc_allocator.c 2022-05-26 03:46:27 UTC (rev 294866)
@@ -23,25 +23,6 @@
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
-//
-// Probabilistic Guard Malloc (PGM) is a new allocator designed to catch use after free attempts and out of bounds accesses.
-// It behaves similarly to AddressSanitizer (ASAN), but aims to have minimal runtime overhead.
-//
-// The design of PGM is quite simple. Each time an allocation is performed an additional guard page is added above and below the newly
-// allocated page(s). An allocation may span multiple pages. When a deallocation is performed, the page(s) allocated will be protected
-// using mprotect to ensure that any use after frees will trigger a crash. Virtual memory addresses are never reused, so we will never run
-// into a case where object 1 is freed, object 2 is allocated over the same address space, and object 1 then accesses the memory address
-// space of now object 2.
-//
-// PGM does add notable memory overhead. Each allocation, no matter the size, adds an additional 2 guard pages (8KB for X86_64 and 32KB
-// for ARM64). In addition, there may be free memory left over in the page(s) allocated for the user. This memory may not be used by any
-// other allocation.
-//
-// We added limits on virtual memory and wasted memory to help limit the memory impact on the overall system. Virtual memory for this
-// allocator is limited to 1GB. Wasted memory, which is the unused memory in the page(s) allocated by the user, is limited to 1MB.
-// These overall limits should ensure that the memory impact on the system is minimal, while helping to tackle the problems of catching
-// use after frees and out of bounds accesses.
-//
#include "pas_config.h"
@@ -57,39 +38,18 @@
#include "pas_large_heap.h"
#include "pas_ptr_hash_map.h"
#include "iso_heap_config.h"
+#include "pas_utility_heap.h"
#include "pas_large_utility_free_heap.h"
-// debug toggle
-static const bool pgm_verbose = false;
+static size_t free_wasted_mem = PAS_PGM_MAX_WASTED_MEMORY;
+static size_t free_virtual_mem = PAS_PGM_MAX_VIRTUAL_MEMORY;
-// max amount of free memory that can be wasted (1MB)
-#define MAX_WASTED_MEMORY (1024 * 1024)
+bool pas_pgm_can_use = true;
-// max amount of virtual memory that can be used by PGM (1GB)
-// including guard pages and wasted memory
-#define MAX_VIRTUAL_MEMORY (1024 * 1024 * 1024)
-
-static bool pgm_enabled = true;
-
-static size_t free_wasted_mem = MAX_WASTED_MEMORY;
-static size_t free_virtual_mem = MAX_VIRTUAL_MEMORY;
-
-// structure for holding metadata of pgm allocations
-typedef struct pgm_storage pgm_storage;
-struct pgm_storage {
- size_t allocation_size_requested;
- size_t size_of_data_pages;
- size_t mem_to_waste;
- size_t mem_to_alloc;
- uintptr_t start_of_data_pages;
- uintptr_t upper_guard_page;
- uintptr_t lower_guard_page;
-};
-
// the hash map is used to keep track of all pgm allocations
// key : user's starting memory address
-// value : metadata for tracking that allocation (pgm_storage)
-pas_ptr_hash_map pgm_hash_map = PAS_HASHTABLE_INITIALIZER;
+// value : metadata for tracking that allocation (pas_pgm_storage)
+pas_ptr_hash_map pas_pgm_hash_map = PAS_HASHTABLE_INITIALIZER;
#if PAS_COMPILER(CLANG)
#pragma mark -
@@ -96,21 +56,25 @@
#pragma mark ALLOC/DEALLOC
#endif
-void* pas_probabilistic_guard_malloc_allocate(size_t size, pas_heap* heap, pas_heap_config* heap_config,
- pas_physical_memory_transaction* transaction) {
+pas_allocation_result pas_probabilistic_guard_malloc_allocate(pas_large_heap* large_heap, size_t size, pas_heap_config* heap_config,
+ pas_physical_memory_transaction* transaction)
+{
pas_heap_lock_assert_held();
+ static const bool verbose = false;
- // input checking
- if (!heap || !size || !heap_config || !transaction)
- return NULL;
+ pas_allocation_result result = pas_allocation_result_create_failure();
- // get page size
+ if (verbose)
+ printf("Memory requested to allocate %zu\n", size);
+
+ if (!large_heap || !size || !heap_config || !transaction)
+ return result;
+
const size_t page_size = pas_page_malloc_alignment();
- // calculate wasted memory
- size_t mem_to_waste = page_size - (size % page_size);
+ size_t mem_to_waste = (page_size - (size % page_size)) % page_size;
if (mem_to_waste > free_wasted_mem)
- return NULL;
+ return result;
// calculate virtual memory
//
@@ -119,13 +83,11 @@
// *------------------* *------------------* *------------------*
size_t mem_to_alloc = (2 * page_size) + size + mem_to_waste;
if (mem_to_alloc > free_virtual_mem)
- return NULL;
+ return result;
- // allocate memory
- pas_allocation_result result = pas_large_heap_try_allocate_and_forget(&heap->large_heap, mem_to_alloc, page_size,
- heap_config, transaction);
+ result = pas_large_heap_try_allocate_and_forget(large_heap, mem_to_alloc, page_size,heap_config, transaction);
if (!result.did_succeed)
- return NULL;
+ return result;
// protect guard pages from being accessed
uintptr_t lower_guard_page = result.begin;
@@ -150,7 +112,7 @@
void * key = (void*) (result.begin + page_size + mem_to_waste);
// create struct to hold hash map value
- pgm_storage *value = malloc(sizeof(pgm_storage));
+ pas_pgm_storage *value = pas_utility_heap_try_allocate(sizeof(pas_pgm_storage), "pas_pgm_hash_map_VALUE");
PAS_ASSERT(value);
value->mem_to_alloc = mem_to_alloc;
@@ -161,65 +123,42 @@
value->start_of_data_pages = result.begin + page_size;
value->allocation_size_requested = size;
- // add to hash map
- pas_ptr_hash_map_add_result add_result = pas_ptr_hash_map_add(&pgm_hash_map, key, NULL,
- &pas_large_utility_free_heap_allocation_config);
+ pas_ptr_hash_map_add_result add_result = pas_ptr_hash_map_add(&pas_pgm_hash_map, key, NULL,&pas_large_utility_free_heap_allocation_config);
PAS_ASSERT(add_result.is_new_entry);
add_result.entry->key = key;
add_result.entry->value = value;
- // update global virtual and wasted memory
free_wasted_mem -= mem_to_waste;
free_virtual_mem -= mem_to_alloc;
- if (pgm_verbose) {
- printf("******************************************************\n"
- " Allocating Memory\n\n"
- " Overall System Stats"
- " free_wasted_mem : %zu\n"
- " free_virtual_mem : %zu\n"
- "\n"
- " Allocation\n"
- " Allocation Size Requested : %zu \n"
- " Memory Allocated : %zu \n"
- " Memory Wasted : %zu \n"
- " Size of Data Pages : %zu \n"
- " Lower Guard Page Address : %p \n"
- " Upper Guard Page Address : %p \n"
- " Start of Data Pages : %p \n"
- " Memory Address for User : %p \n"
- "******************************************************\n\n\n",
- free_wasted_mem,
- free_virtual_mem,
- value->allocation_size_requested,
- value->mem_to_alloc,
- value->mem_to_waste,
- value->size_of_data_pages,
- (uintptr_t *) value->lower_guard_page,
- (uintptr_t *) value->upper_guard_page,
- (uintptr_t *) value->start_of_data_pages,
- key);
- }
+ if (verbose)
+ pas_probabilistic_guard_malloc_debug_info(key, value, "Allocating memory");
- return key;
+ result.begin = (uintptr_t)key;
+
+ // 3 pages are the minimum required for PGM
+ if (free_virtual_mem < 3 * page_size)
+ pas_pgm_can_use = false;
+
+ return result;
}
-void pas_probabilistic_guard_malloc_deallocate(void* mem) {
+void pas_probabilistic_guard_malloc_deallocate(void* mem)
+{
pas_heap_lock_assert_held();
+ static const bool verbose = false;
- if (pgm_verbose)
+ if (verbose)
printf("Memory Address Requested to Deallocate %p\n", mem);
uintptr_t * key = (uintptr_t *) mem;
- // get value from hash map
- pas_ptr_hash_map_entry * entry = pas_ptr_hash_map_find(&pgm_hash_map, key);
+ pas_ptr_hash_map_entry * entry = pas_ptr_hash_map_find(&pas_pgm_hash_map, key);
if (!entry || !entry->value)
return;
- // protect the pages
- pgm_storage * value = (pgm_storage *) entry->value;
+ pas_pgm_storage * value = (pas_pgm_storage *) entry->value;
int mprotect_res = mprotect( (void *) value->start_of_data_pages, value->size_of_data_pages, PROT_NONE);
PAS_ASSERT(!mprotect_res);
@@ -228,91 +167,79 @@
int madvise_res = madvise((void *) value->start_of_data_pages, value->size_of_data_pages, MADV_FREE);
PAS_ASSERT(!madvise_res);
- // remove value from hash map
- bool removed = pas_ptr_hash_map_remove(&pgm_hash_map, key, NULL, &pas_large_utility_free_heap_allocation_config);
+ bool removed = pas_ptr_hash_map_remove(&pas_pgm_hash_map, key, NULL, &pas_large_utility_free_heap_allocation_config);
PAS_ASSERT(removed);
- // update global virtual and wasted memory
free_wasted_mem += value->mem_to_waste;
free_virtual_mem += value->mem_to_alloc;
- if (pgm_verbose) {
- printf("******************************************************\n"
- " Deallocating Memory\n\n"
- " Overall System Stats"
- " free_wasted_mem : %zu\n"
- " free_virtual_mem : %zu\n"
- "\n"
- " Deallocation\n"
- " Allocation Size Requested : %zu \n"
- " Memory Allocated : %zu \n"
- " Memory Wasted : %zu \n"
- " Size of Data Pages : %zu \n"
- " Lower Guard Page Address : %p \n"
- " Upper Guard Page Address : %p \n"
- " Start of Data Pages : %p \n"
- " Memory Address for User : %p \n"
- "******************************************************\n\n\n",
- free_wasted_mem,
- free_virtual_mem,
- value->allocation_size_requested,
- value->mem_to_alloc,
- value->mem_to_waste,
- value->size_of_data_pages,
- (uintptr_t *) value->lower_guard_page,
- (uintptr_t *) value->upper_guard_page,
- (uintptr_t *) value->start_of_data_pages,
- key);
- }
+ if (verbose)
+ pas_probabilistic_guard_malloc_debug_info(key, value, "Deallocating Memory");
- // free memory
- free(value);
-}
+ pas_pgm_can_use = true;
-
-#if PAS_COMPILER(CLANG)
-#pragma mark -
-#pragma mark Determine whether to use PGM
-#endif
-
-void pas_probabilistic_guard_malloc_trigger(void) {
- // ???
+ pas_utility_heap_deallocate(value);
}
-bool pas_probabilistic_guard_malloc_can_use(void) {
+bool pas_probabilistic_guard_malloc_check_exists(uintptr_t mem)
+{
pas_heap_lock_assert_held();
+ static const bool verbose = false;
- if (!pgm_enabled)
- return false;
+ if (verbose)
+ printf("Checking if is PGM entry\n");
- if (!free_wasted_mem || !free_virtual_mem)
- return false;
-
- return true;
+ pas_ptr_hash_map_entry * entry = pas_ptr_hash_map_find(&pas_pgm_hash_map, (void *) mem);
+ return (entry && entry->value);
}
-bool pas_probabilistic_guard_malloc_should_use(void) {
- pas_heap_lock_assert_held();
- if (!pgm_enabled)
- return false;
-
- return true;
-}
-
#if PAS_COMPILER(CLANG)
#pragma mark -
#pragma mark Helper Functions
#endif
-size_t pas_probabilistic_guard_malloc_get_free_virtual_memory() {
+size_t pas_probabilistic_guard_malloc_get_free_virtual_memory()
+{
pas_heap_lock_assert_held();
return free_virtual_mem;
}
-size_t pas_probabilistic_guard_malloc_get_free_wasted_memory() {
+size_t pas_probabilistic_guard_malloc_get_free_wasted_memory()
+{
pas_heap_lock_assert_held();
return free_wasted_mem;
}
+static PAS_ALWAYS_INLINE void pas_probabilistic_guard_malloc_debug_info(const void *key, const pas_pgm_storage *value, const char *operation)
+{
+ printf("******************************************************\n"
+ " %s\n\n"
+ " Overall System Stats"
+ " free_wasted_mem : %zu\n"
+ " free_virtual_mem : %zu\n"
+ "\n"
+ " Allocation\n"
+ " Allocation Size Requested : %zu \n"
+ " Memory Allocated : %zu \n"
+ " Memory Wasted : %zu \n"
+ " Size of Data Pages : %zu \n"
+ " Lower Guard Page Address : %p \n"
+ " Upper Guard Page Address : %p \n"
+ " Start of Data Pages : %p \n"
+ " Memory Address for User : %p \n"
+ "******************************************************\n\n\n",
+ operation,
+ free_wasted_mem,
+ free_virtual_mem,
+ value->allocation_size_requested,
+ value->mem_to_alloc,
+ value->mem_to_waste,
+ value->size_of_data_pages,
+ (uintptr_t *) value->lower_guard_page,
+ (uintptr_t *) value->upper_guard_page,
+ (uintptr_t *) value->start_of_data_pages,
+ key);
+}
+
#endif /* LIBPAS_ENABLED */
Modified: trunk/Source/bmalloc/libpas/src/libpas/pas_probabilistic_guard_malloc_allocator.h (294865 => 294866)
--- trunk/Source/bmalloc/libpas/src/libpas/pas_probabilistic_guard_malloc_allocator.h 2022-05-26 03:39:27 UTC (rev 294865)
+++ trunk/Source/bmalloc/libpas/src/libpas/pas_probabilistic_guard_malloc_allocator.h 2022-05-26 03:46:27 UTC (rev 294866)
@@ -28,22 +28,49 @@
#define PAS_PROBABILISTIC_GUARD_MALLOC_ALLOCATOR
#include "pas_utils.h"
+#include "pas_large_heap.h"
+#include <stdbool.h>
PAS_BEGIN_EXTERN_C;
-/* Initial Function Definitions */
+// structure for holding metadata of pgm allocations
+// FIXME : Reduce size of structure
+typedef struct pas_pgm_storage pas_pgm_storage;
+struct pas_pgm_storage {
+ size_t allocation_size_requested;
+ size_t size_of_data_pages;
+ size_t mem_to_waste;
+ size_t mem_to_alloc;
+ uintptr_t start_of_data_pages;
+ uintptr_t upper_guard_page;
+ uintptr_t lower_guard_page;
+};
-void pas_probabilistic_guard_malloc_trigger(void);
-bool pas_probabilistic_guard_malloc_can_use(void);
-bool pas_probabilistic_guard_malloc_should_use(void);
+// max amount of free memory that can be wasted (1MB)
+#define PAS_PGM_MAX_WASTED_MEMORY (1024 * 1024)
-void* pas_probabilistic_guard_malloc_allocate(size_t size, pas_heap* heap, pas_heap_config* heap_config, pas_physical_memory_transaction* transaction);
+// max amount of virtual memory that can be used by PGM (1GB)
+// including guard pages and wasted memory
+#define PAS_PGM_MAX_VIRTUAL_MEMORY (1024 * 1024 * 1024)
+
+// Probability that we should call PGM in percentage (0-100)
+#define PAS_PGM_PROBABILITY (1)
+
+/* We want a fast way to determine if we can call PGM or not.
+ * It would be really wasteful to recompute this answer each time we try to allocate,
+ * so just update this variable each time we allocate or deallocate. */
+extern PAS_API bool pas_pgm_can_use;
+
+pas_allocation_result pas_probabilistic_guard_malloc_allocate(pas_large_heap* large_heap, size_t size, pas_heap_config* heap_config, pas_physical_memory_transaction* transaction);
void pas_probabilistic_guard_malloc_deallocate(void* memory);
-/* Helper functions */
size_t pas_probabilistic_guard_malloc_get_free_virtual_memory(void);
size_t pas_probabilistic_guard_malloc_get_free_wasted_memory(void);
+bool pas_probabilistic_guard_malloc_check_exists(uintptr_t mem);
+
+static PAS_ALWAYS_INLINE void pas_probabilistic_guard_malloc_debug_info(const void *key, const pas_pgm_storage *value, const char *operation);
+
PAS_END_EXTERN_C;
#endif
Modified: trunk/Source/bmalloc/libpas/src/libpas/pas_random.h (294865 => 294866)
--- trunk/Source/bmalloc/libpas/src/libpas/pas_random.h 2022-05-26 03:39:27 UTC (rev 294865)
+++ trunk/Source/bmalloc/libpas/src/libpas/pas_random.h 2022-05-26 03:46:27 UTC (rev 294866)
@@ -31,26 +31,15 @@
PAS_BEGIN_EXTERN_C;
-enum pas_random_kind {
- /* This is a PRNG optimized for speed and nothing else. It's used whenever we need a random
- number only as a performance optimization. */
- pas_fast_random,
-
- /* This is a PRNG optimized for security. It's used whenever we need unpredictable data.
- This will incur significant performance penalties over pas_fast_random. */
- pas_secure_random
-};
-
-typedef enum pas_random_kind pas_random_kind;
-
extern PAS_API unsigned pas_fast_random_state;
/* This is useful for testing. */
extern PAS_API unsigned (*pas_mock_fast_random)(void);
-/* Returns a random number in [0, upper_bound).
- If the upper_bound is set to zero, than the range shall be [0, UINT32_MAX). */
-static inline unsigned pas_get_random(pas_random_kind kind, unsigned upper_bound)
+/* This is a PRNG optimized for speed and nothing else. It's used whenever we need a random number only as a
+ performance optimization. Returns a random number in [0, upper_bound). If the upper_bound is set to zero, than
+ the range shall be [0, UINT32_MAX). */
+static inline unsigned pas_get_fast_random(unsigned upper_bound)
{
unsigned rand_value;
@@ -57,31 +46,36 @@
if (!upper_bound)
upper_bound = UINT32_MAX;
- switch (kind) {
- case pas_fast_random:
- if (PAS_LIKELY(!pas_mock_fast_random)) {
- pas_fast_random_state = pas_xorshift32(pas_fast_random_state);
- rand_value = pas_fast_random_state % upper_bound;
- } else {
- /* This is testing code. It will not be called during regular code flow. */
- rand_value = pas_mock_fast_random() % upper_bound;
- }
+ if (PAS_LIKELY(!pas_mock_fast_random)) {
+ pas_fast_random_state = pas_xorshift32(pas_fast_random_state);
+ rand_value = pas_fast_random_state % upper_bound;
+ } else {
+ /* This is testing code. It will not be called during regular code flow. */
+ rand_value = pas_mock_fast_random() % upper_bound;
+ }
- break;
+ return rand_value;
+}
- case pas_secure_random:
- /* Secure random is only supported on Darwin and FreeBSD at the moment due to arc4random being built into the
- stdlib. Fall back to fast behavior on other operating systems. */
+/* This is a PRNG optimized for security. It's used whenever we need unpredictable data. This will incur significant
+ performance penalties over pas_fast_random. Returns a random number in [0, upper_bound). If the upper_bound is set
+ to zero, than the range shall be [0, UINT32_MAX). */
+static inline unsigned pas_get_secure_random(unsigned upper_bound)
+{
+ unsigned rand_value;
+
+ if (!upper_bound)
+ upper_bound = UINT32_MAX;
+
+ /* Secure random is only supported on Darwin and FreeBSD at the moment due to arc4random being built into the
+ stdlib. Fall back to fast behavior on other operating systems. */
#if PAS_OS(DARWIN) || (PAS_OS(FREEBSD) && !PAS_PLATFORM(PLAYSTATION))
- rand_value = arc4random_uniform(upper_bound);
+ rand_value = arc4random_uniform(upper_bound);
#else
- pas_fast_random_state = pas_xorshift32(pas_fast_random_state);
- rand_value = pas_fast_random_state % upper_bound;
+ pas_fast_random_state = pas_xorshift32(pas_fast_random_state);
+ rand_value = pas_fast_random_state % upper_bound;
#endif
- break;
- }
-
return rand_value;
}
@@ -88,4 +82,3 @@
PAS_END_EXTERN_C;
#endif /* PAS_RANDOM_H */
-
Modified: trunk/Source/bmalloc/libpas/src/libpas/pas_segregated_shared_page_directory.c (294865 => 294866)
--- trunk/Source/bmalloc/libpas/src/libpas/pas_segregated_shared_page_directory.c 2022-05-26 03:39:27 UTC (rev 294865)
+++ trunk/Source/bmalloc/libpas/src/libpas/pas_segregated_shared_page_directory.c 2022-05-26 03:46:27 UTC (rev 294866)
@@ -95,7 +95,7 @@
return true;
}
- if (pas_get_random(pas_fast_random, 0)
+ if (pas_get_fast_random(0)
<= pas_segregated_shared_page_directory_probability_of_ineligibility) {
if (verbose)
pas_log("cannot bump at %zu, clearing eligibility.\n", config->index);
Modified: trunk/Source/bmalloc/libpas/src/libpas/thingy_heap_config.h (294865 => 294866)
--- trunk/Source/bmalloc/libpas/src/libpas/thingy_heap_config.h 2022-05-26 03:39:27 UTC (rev 294865)
+++ trunk/Source/bmalloc/libpas/src/libpas/thingy_heap_config.h 2022-05-26 03:46:27 UTC (rev 294866)
@@ -75,7 +75,8 @@
.medium_bitfit_min_align_shift = PAS_MIN_MEDIUM_ALIGN_SHIFT, \
.use_marge_bitfit = true, \
.marge_bitfit_min_align_shift = PAS_MIN_MARGE_ALIGN_SHIFT, \
- .marge_bitfit_page_size = PAS_MARGE_PAGE_DEFAULT_SIZE)
+ .marge_bitfit_page_size = PAS_MARGE_PAGE_DEFAULT_SIZE, \
+ .pgm_enabled = false)
extern PAS_API pas_heap_config thingy_heap_config;
Modified: trunk/Source/bmalloc/libpas/src/test/IsoHeapPartialAndBaselineTests.cpp (294865 => 294866)
--- trunk/Source/bmalloc/libpas/src/test/IsoHeapPartialAndBaselineTests.cpp 2022-05-26 03:39:27 UTC (rev 294865)
+++ trunk/Source/bmalloc/libpas/src/test/IsoHeapPartialAndBaselineTests.cpp 2022-05-26 03:46:27 UTC (rev 294866)
@@ -91,7 +91,7 @@
size_t getNext() const override
{
PAS_ASSERT(!m_indices.empty());
- size_t index = pas_get_random(pas_fast_random, static_cast<unsigned>(m_indices.size()));
+ size_t index = pas_get_fast_random(static_cast<unsigned>(m_indices.size()));
size_t result = m_indices[index];
m_indices[index] = m_indices.back();
m_indices.pop_back();
Modified: trunk/Source/bmalloc/libpas/src/test/PGMTests.cpp (294865 => 294866)
--- trunk/Source/bmalloc/libpas/src/test/PGMTests.cpp 2022-05-26 03:39:27 UTC (rev 294865)
+++ trunk/Source/bmalloc/libpas/src/test/PGMTests.cpp 2022-05-26 03:46:27 UTC (rev 294866)
@@ -45,25 +45,25 @@
pas_heap_lock_lock();
- size_t init_free_virt_mem = pas_probabilistic_guard_malloc_get_free_virtual_memory();
+ size_t init_free_virtual_mem = pas_probabilistic_guard_malloc_get_free_virtual_memory();
size_t init_free_wasted_mem = pas_probabilistic_guard_malloc_get_free_wasted_memory();
size_t alloc_size = 1024;
- void * mem = pas_probabilistic_guard_malloc_allocate(alloc_size, heap, &iso_heap_config, &transaction);
- CHECK(mem);
+ pas_allocation_result result = pas_probabilistic_guard_malloc_allocate(&heap->large_heap, alloc_size, &iso_heap_config, &transaction);
+ CHECK(result.begin);
- size_t updated_free_virt_mem = pas_probabilistic_guard_malloc_get_free_virtual_memory();
+ size_t updated_free_virtual_mem = pas_probabilistic_guard_malloc_get_free_virtual_memory();
size_t updated_free_wasted_mem = pas_probabilistic_guard_malloc_get_free_wasted_memory();
- CHECK_EQUAL(init_free_virt_mem - (3 * getpagesize()), updated_free_virt_mem);
+ CHECK_EQUAL(init_free_virtual_mem - (3 * getpagesize()), updated_free_virtual_mem);
CHECK_EQUAL(init_free_wasted_mem - (getpagesize() - alloc_size), updated_free_wasted_mem);
- pas_probabilistic_guard_malloc_deallocate(mem);
+ pas_probabilistic_guard_malloc_deallocate(reinterpret_cast<void *>(result.begin));
- updated_free_virt_mem = pas_probabilistic_guard_malloc_get_free_virtual_memory();
+ updated_free_virtual_mem = pas_probabilistic_guard_malloc_get_free_virtual_memory();
updated_free_wasted_mem = pas_probabilistic_guard_malloc_get_free_wasted_memory();
- CHECK_EQUAL(init_free_virt_mem, updated_free_virt_mem);
+ CHECK_EQUAL(init_free_virtual_mem, updated_free_virtual_mem);
CHECK_EQUAL(init_free_wasted_mem, updated_free_wasted_mem);
pas_heap_lock_unlock();
@@ -79,27 +79,27 @@
pas_heap_lock_lock();
- size_t init_free_virt_mem = pas_probabilistic_guard_malloc_get_free_virtual_memory();
+ size_t init_free_virtual_mem = pas_probabilistic_guard_malloc_get_free_virtual_memory();
size_t init_free_wasted_mem = pas_probabilistic_guard_malloc_get_free_wasted_memory();
size_t num_allocations = 100;
- void* mem_storage[num_allocations];
+ pas_allocation_result mem_storage[num_allocations];
for (size_t i = 0; i < num_allocations; i++ ) {
size_t alloc_size = random() % 100000;
- mem_storage[i] = pas_probabilistic_guard_malloc_allocate(alloc_size, heap, &iso_heap_config, &transaction);
- void * mem = mem_storage[i];
- memset(mem, 0x42, alloc_size);
+ mem_storage[i] = pas_probabilistic_guard_malloc_allocate(&heap->large_heap, alloc_size, &iso_heap_config, &transaction);
+ pas_allocation_result mem = mem_storage[i];
+ memset(reinterpret_cast<void *>(mem.begin), 0x42, alloc_size);
}
for (size_t i = 0; i < num_allocations; i++ ) {
- pas_probabilistic_guard_malloc_deallocate(mem_storage[i]);
+ pas_probabilistic_guard_malloc_deallocate(reinterpret_cast<void *>(mem_storage[i].begin));
}
- size_t updated_free_virt_mem = pas_probabilistic_guard_malloc_get_free_virtual_memory();
+ size_t updated_free_virtual_mem = pas_probabilistic_guard_malloc_get_free_virtual_memory();
size_t updated_free_wasted_mem = pas_probabilistic_guard_malloc_get_free_wasted_memory();
- CHECK_EQUAL(init_free_virt_mem, updated_free_virt_mem);
+ CHECK_EQUAL(init_free_virtual_mem, updated_free_virtual_mem);
CHECK_EQUAL(init_free_wasted_mem, updated_free_wasted_mem);
pas_heap_lock_unlock();
@@ -114,46 +114,51 @@
pas_heap_lock_lock();
- void *mem = NULL;
+ pas_allocation_result result;
// Test invalid alloc size
- mem = pas_probabilistic_guard_malloc_allocate(0, heap, &iso_heap_config, &transaction);
- CHECK(!mem);
+ result = pas_probabilistic_guard_malloc_allocate(&heap->large_heap, 0, &iso_heap_config, &transaction);
+ CHECK(!result.begin);
+ CHECK(!result.did_succeed);
// Test NULL heap
- mem = pas_probabilistic_guard_malloc_allocate(1024, NULL, &iso_heap_config, &transaction);
- CHECK(!mem);
+ result = pas_probabilistic_guard_malloc_allocate(nullptr, 1024, &iso_heap_config, &transaction);
+ CHECK(!result.begin);
+ CHECK(!result.did_succeed);
// Test allocating more than virtual memory available
- mem = pas_probabilistic_guard_malloc_allocate(1024 * 1024 * 1024 + 1, NULL, &iso_heap_config, &transaction);
- CHECK(!mem);
+ result = pas_probabilistic_guard_malloc_allocate(nullptr, 1024 * 1024 * 1024 + 1, &iso_heap_config, &transaction);
+ CHECK(!result.begin);
+ CHECK(!result.did_succeed);
// Test allocating when wasted memory is full
size_t num_allocations = 1000;
- void* mem_storage[num_allocations];
+ pas_allocation_result mem_storage[num_allocations];
for (size_t i = 0; i < num_allocations; i++ ) {
size_t alloc_size = 1; // A small alloc size wastes more memory
- mem_storage[i] = pas_probabilistic_guard_malloc_allocate(alloc_size, heap, &iso_heap_config, &transaction);
+ mem_storage[i] = pas_probabilistic_guard_malloc_allocate(&heap->large_heap, alloc_size, &iso_heap_config, &transaction);
}
- mem = pas_probabilistic_guard_malloc_allocate(1, heap, &iso_heap_config, &transaction);
- CHECK(!mem);
+ result = pas_probabilistic_guard_malloc_allocate(&heap->large_heap, 1, &iso_heap_config, &transaction);
+ CHECK(!result.begin);
+ CHECK(!result.did_succeed);
for (size_t i = 0; i < num_allocations; i++ ) {
- pas_probabilistic_guard_malloc_deallocate(mem_storage[i]);
+ pas_probabilistic_guard_malloc_deallocate(reinterpret_cast<void *>(mem_storage[i].begin));
}
// Test deallocating invalid memory locations
- pas_probabilistic_guard_malloc_deallocate(NULL);
+ pas_probabilistic_guard_malloc_deallocate(nullptr);
pas_probabilistic_guard_malloc_deallocate((void *) -1);
pas_probabilistic_guard_malloc_deallocate((void *) 0x42);
// Test deallocating same memory location multiple times
- mem = pas_probabilistic_guard_malloc_allocate(1, heap, &iso_heap_config, &transaction);
- CHECK(mem);
+ result = pas_probabilistic_guard_malloc_allocate(&heap->large_heap, 1, &iso_heap_config, &transaction);
+ CHECK(result.begin);
+ CHECK(result.did_succeed);
- pas_probabilistic_guard_malloc_deallocate(mem);
- pas_probabilistic_guard_malloc_deallocate(mem);
+ pas_probabilistic_guard_malloc_deallocate(reinterpret_cast<void *>(result.begin));
+ pas_probabilistic_guard_malloc_deallocate(reinterpret_cast<void *>(result.begin));
pas_heap_lock_unlock();
}
