- Revision
- 293518
- Author
- brandonstew...@apple.com
- Date
- 2022-04-27 10:30:22 -0700 (Wed, 27 Apr 2022)
Log Message
[libpas] Implement secure random numbers
https://bugs.webkit.org/show_bug.cgi?id=239735
Reviewed by Yusuke Suzuki.
We currently have a cheesy random and secure random, which use the same implementation for generating
random numbers. (We are going to ignore the mock testing code here). This patch introduces a fast random and
secure random. The fast random maintains the same properties as the previous implementation, while secure random
will use the cryptographically secure arc4random_uniform to give better randomness. arc4random() can be quite an
expensive operation and based on discussing with Yusuke he found heavy performance penalties when using this in
JSC. Our secure random shall only be used in cases where true randomness is needed. We have 2 spots where we
currently use secure random; we shall just migrate those over to using fast random.
* Source/bmalloc/libpas/src/libpas/pas_baseline_allocator_table.c:
(pas_baseline_allocator_table_get_random_index):
* Source/bmalloc/libpas/src/libpas/pas_dynamic_primitive_heap_map.c:
(pas_dynamic_primitive_heap_map_find_slow):
* Source/bmalloc/libpas/src/libpas/pas_random.c:
* Source/bmalloc/libpas/src/libpas/pas_random.h:
(pas_get_random):
* Source/bmalloc/libpas/src/libpas/pas_segregated_shared_page_directory.c:
(find_first_eligible_consider_view):
* Source/bmalloc/libpas/src/test/IsoHeapPartialAndBaselineTests.cpp:
(std::testTwoBaselinesEvictions):
Canonical link: https://commits.webkit.org/250049@main
Modified Paths
Diff
Modified: trunk/Source/bmalloc/ChangeLog (293517 => 293518)
--- trunk/Source/bmalloc/ChangeLog 2022-04-27 17:26:47 UTC (rev 293517)
+++ trunk/Source/bmalloc/ChangeLog 2022-04-27 17:30:22 UTC (rev 293518)
@@ -1,3 +1,30 @@
+2022-04-25 Brandon Stewart <brandonstew...@apple.com>
+
+ [libpas] Implement secure random numbers
+ https://bugs.webkit.org/show_bug.cgi?id=239735
+
+ Reviewed by Yusuke Suzuki.
+
+ We currently have a cheesy random and secure random, which use the same implementation for generating
+ random numbers. (We are going to ignore the mock testing code here). This patch introduces a fast random and
+ secure random. The fast random maintains the same properties as the previous implementation, while secure random
+ will use the cryptographically secure arc4random_uniform to give better randomness. arc4random() can be quite an
+ expensive operation and based on discussing with Yusuke he found heavy performance penalties when using this in
+ JSC. Our secure random shall only be used in cases where true randomness is needed. We have 2 spots where we
+ currently use secure random we shall just migrate those over to using fast random.
+
+ * libpas/src/libpas/pas_baseline_allocator_table.c:
+ (pas_baseline_allocator_table_get_random_index):
+ * libpas/src/libpas/pas_dynamic_primitive_heap_map.c:
+ (pas_dynamic_primitive_heap_map_find_slow):
+ * libpas/src/libpas/pas_random.c:
+ * libpas/src/libpas/pas_random.h:
+ (pas_get_random):
+ * libpas/src/libpas/pas_segregated_shared_page_directory.c:
+ (find_first_eligible_consider_view):
+ * libpas/src/test/IsoHeapPartialAndBaselineTests.cpp:
+ (std::testTwoBaselinesEvictions):
+
2022-04-18 Elliott Williams <e...@apple.com>
[XCBuild] Use XCBuild for all command-line and project builds
Modified: trunk/Source/bmalloc/libpas/src/libpas/pas_baseline_allocator_table.c (293517 => 293518)
--- trunk/Source/bmalloc/libpas/src/libpas/pas_baseline_allocator_table.c 2022-04-27 17:26:47 UTC (rev 293517)
+++ trunk/Source/bmalloc/libpas/src/libpas/pas_baseline_allocator_table.c 2022-04-27 17:30:22 UTC (rev 293518)
@@ -63,7 +63,7 @@
unsigned pas_baseline_allocator_table_get_random_index(void)
{
- return pas_get_random(pas_cheesy_random, PAS_MIN(PAS_NUM_BASELINE_ALLOCATORS,
+ return pas_get_random(pas_fast_random, PAS_MIN(PAS_NUM_BASELINE_ALLOCATORS,
pas_baseline_allocator_table_bound));
}
Modified: trunk/Source/bmalloc/libpas/src/libpas/pas_dynamic_primitive_heap_map.c (293517 => 293518)
--- trunk/Source/bmalloc/libpas/src/libpas/pas_dynamic_primitive_heap_map.c 2022-04-27 17:26:47 UTC (rev 293517)
+++ trunk/Source/bmalloc/libpas/src/libpas/pas_dynamic_primitive_heap_map.c 2022-04-27 17:30:22 UTC (rev 293518)
@@ -87,13 +87,13 @@
being dynamically changed. We try to allow that. */
result = heaps_for_size->heaps[
- pas_get_random(pas_secure_random, heaps_for_size->num_heaps)];
+ pas_get_random(pas_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_secure_random, map->num_heaps)];
+ result = map->heaps[pas_get_random(pas_fast_random, map->num_heaps)];
} else {
pas_simple_type_with_key_data* key_data;
Modified: trunk/Source/bmalloc/libpas/src/libpas/pas_random.c (293517 => 293518)
--- trunk/Source/bmalloc/libpas/src/libpas/pas_random.c 2022-04-27 17:26:47 UTC (rev 293517)
+++ trunk/Source/bmalloc/libpas/src/libpas/pas_random.c 2022-04-27 17:30:22 UTC (rev 293518)
@@ -29,7 +29,7 @@
#include "pas_random.h"
-unsigned pas_cheesy_random_state = 42;
-unsigned (*pas_mock_cheesy_random)(void) = NULL;
+unsigned pas_fast_random_state = 42;
+unsigned (*pas_mock_fast_random)(void) = NULL;
#endif /* LIBPAS_ENABLED */
Modified: trunk/Source/bmalloc/libpas/src/libpas/pas_random.h (293517 => 293518)
--- trunk/Source/bmalloc/libpas/src/libpas/pas_random.h 2022-04-27 17:26:47 UTC (rev 293517)
+++ trunk/Source/bmalloc/libpas/src/libpas/pas_random.h 2022-04-27 17:30:22 UTC (rev 293518)
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2019 Apple Inc. All rights reserved.
+ * Copyright (c) 2019-2022 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -27,6 +27,7 @@
#define PAS_RANDOM_H
#include "pas_utils.h"
+#include <stdlib.h>
PAS_BEGIN_EXTERN_C;
@@ -33,41 +34,55 @@
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_cheesy_random,
+ pas_fast_random,
/* This is a PRNG optimized for security. It's used whenever we need unpredictable data.
-
- FIXME: Implement this. */
+ 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_cheesy_random_state;
+extern PAS_API unsigned pas_fast_random_state;
/* This is useful for testing. */
-extern PAS_API unsigned (*pas_mock_cheesy_random)(void);
+extern PAS_API unsigned (*pas_mock_fast_random)(void);
-/* Returns a random number in [0, upper_bound). If upper_bound is zero, returns a number somewhere
- in the whole unsigned range. */
+/* 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)
{
- unsigned current_state;
-
- /* FIXME: Need to do something different if kind is pas_secure_random. */
- /* FIXME: Need to do something other than modulo for dealing with max_value. */
+ unsigned rand_value;
- if (kind == pas_cheesy_random && pas_mock_cheesy_random)
- current_state = pas_mock_cheesy_random();
- else {
- current_state = pas_xorshift32(pas_cheesy_random_state);
- pas_cheesy_random_state = current_state;
+ 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;
+ }
+
+ break;
+
+ 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. */
+ #if PAS_OS(DARWIN) || PAS_OS(FREEBSD)
+ 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;
+ #endif
+
+ break;
}
- if (!upper_bound)
- return current_state;
-
- return current_state % upper_bound;
+ return rand_value;
}
PAS_END_EXTERN_C;
Modified: trunk/Source/bmalloc/libpas/src/libpas/pas_segregated_shared_page_directory.c (293517 => 293518)
--- trunk/Source/bmalloc/libpas/src/libpas/pas_segregated_shared_page_directory.c 2022-04-27 17:26:47 UTC (rev 293517)
+++ trunk/Source/bmalloc/libpas/src/libpas/pas_segregated_shared_page_directory.c 2022-04-27 17:30:22 UTC (rev 293518)
@@ -95,7 +95,7 @@
return true;
}
- if (pas_get_random(pas_cheesy_random, 0)
+ if (pas_get_random(pas_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/test/IsoHeapPartialAndBaselineTests.cpp (293517 => 293518)
--- trunk/Source/bmalloc/libpas/src/test/IsoHeapPartialAndBaselineTests.cpp 2022-04-27 17:26:47 UTC (rev 293517)
+++ trunk/Source/bmalloc/libpas/src/test/IsoHeapPartialAndBaselineTests.cpp 2022-04-27 17:30:22 UTC (rev 293518)
@@ -91,7 +91,7 @@
size_t getNext() const override
{
PAS_ASSERT(!m_indices.empty());
- size_t index = pas_get_random(pas_cheesy_random, static_cast<unsigned>(m_indices.size()));
+ size_t index = pas_get_random(pas_fast_random, static_cast<unsigned>(m_indices.size()));
size_t result = m_indices[index];
m_indices[index] = m_indices.back();
m_indices.pop_back();
@@ -764,7 +764,7 @@
pas_heap_ref heap2 = ISO_HEAP_REF_INITIALIZER(size2);
vector<void*> objects;
- pas_mock_cheesy_random = random;
+ pas_mock_fast_random = random;
for (size_t index = 0; index < count; ++index) {
objects.push_back(iso_allocate(&heap1));
