[haiku-commits] BRANCH pdziepak-github.aslr - src/system/kernel/vm headers/os/kernel
- From: pdziepak-github.aslr <community@xxxxxxxxxxxx>
- To: haiku-commits@xxxxxxxxxxxxx
- Date: Wed, 27 Feb 2013 01:45:38 +0100 (CET)
added 2 changesets to branch 'refs/remotes/pdziepak-github/aslr'
old head: ff6d12fc57686c163088393ed8d9ca5d5a366086
new head: 7547e2596e8c89c28c4c2bde263ca132bbe61f31
overview: https://github.com/pdziepak/Haiku/compare/ff6d12f...7547e25
----------------------------------------------------------------------------
f6a9ded: vm: implement B_RANDOMIZED_BASE_ADDRESS address specification
B_RAND_BASE_ADDRESS is basically B_BASE_ADDRESS with non-deterministic created
area's base address.
Initial start address is randomized and then the algorithm looks for a large
enough free space in the interval [randomized start, end]. If it fails then
the search is repeated in the interval [original start, randomized start]. In
case it also fails the algorithm falls back to B_ANY_ADDRESS
(B_RANDOMIZED_ANY_ADDRESS when it is implemented) just like B_BASE_ADDRESS
does.
Randomization range is limited by kMaxRandomize and kMaxInitialRandomize.
7547e25: vm: implement B_RANDOMIZED_ANY_ADDRESS address specification
Randomized equivalent of B_ANY_ADDRESS. When a free space is found (as in
B_ANY_ADDRESS) the base adress is then randomized using _RandomizeAddress
pretty much like it is done in B_RANDOMIZED_BASE_ADDRESS.
[ Pawel Dziepak <pdziepak@xxxxxxxxxxx> ]
----------------------------------------------------------------------------
4 files changed, 163 insertions(+), 15 deletions(-)
headers/os/kernel/OS.h | 13 +-
src/system/kernel/vm/VMUserAddressSpace.cpp | 157 ++++++++++++++++++++++--
src/system/kernel/vm/VMUserAddressSpace.h | 6 +
src/system/kernel/vm/vm.cpp | 2 +
############################################################################
Commit: f6a9ded64e799ca96a37ace7d5021a6a38e44b38
Author: Pawel Dziepak <pdziepak@xxxxxxxxxxx>
Date: Mon Feb 25 21:40:05 2013 UTC
vm: implement B_RANDOMIZED_BASE_ADDRESS address specification
B_RAND_BASE_ADDRESS is basically B_BASE_ADDRESS with non-deterministic created
area's base address.
Initial start address is randomized and then the algorithm looks for a large
enough free space in the interval [randomized start, end]. If it fails then
the search is repeated in the interval [original start, randomized start]. In
case it also fails the algorithm falls back to B_ANY_ADDRESS
(B_RANDOMIZED_ANY_ADDRESS when it is implemented) just like B_BASE_ADDRESS does.
Randomization range is limited by kMaxRandomize and kMaxInitialRandomize.
----------------------------------------------------------------------------
diff --git a/headers/os/kernel/OS.h b/headers/os/kernel/OS.h
index d5441da..e65dc1b 100644
--- a/headers/os/kernel/OS.h
+++ b/headers/os/kernel/OS.h
@@ -73,11 +73,14 @@ typedef struct area_info {
#define B_32_BIT_CONTIGUOUS 6 /* B_CONTIGUOUS, < 4 GB
physical address */
/* address spec for create_area(), and clone_area() */
-#define B_ANY_ADDRESS 0
-#define B_EXACT_ADDRESS 1
-#define B_BASE_ADDRESS 2
-#define B_CLONE_ADDRESS 3
-#define B_ANY_KERNEL_ADDRESS 4
+#define B_ANY_ADDRESS 0
+#define B_EXACT_ADDRESS 1
+#define B_BASE_ADDRESS 2
+#define B_CLONE_ADDRESS 3
+#define B_ANY_KERNEL_ADDRESS 4
+/* B_ANY_KERNEL_BLOCK_ADDRESS 5 */
+/* B_RANDOMIZED_ANY_ADDRESS 6 */
+#define B_RANDOMIZED_BASE_ADDRESS 7
/* area protection */
#define B_READ_AREA 1
diff --git a/src/system/kernel/vm/VMUserAddressSpace.cpp
b/src/system/kernel/vm/VMUserAddressSpace.cpp
index 32730a4..8e45bec 100644
--- a/src/system/kernel/vm/VMUserAddressSpace.cpp
+++ b/src/system/kernel/vm/VMUserAddressSpace.cpp
@@ -29,6 +29,15 @@
#endif
+#ifdef B_HAIKU_64_BIT
+const addr_t VMUserAddressSpace::kMaxRandomize =
0x8000000000ul;
+const addr_t VMUserAddressSpace::kMaxInitialRandomize = 0x20000000000ul;
+#else
+const addr_t VMUserAddressSpace::kMaxRandomize = 0x800000ul;
+const addr_t VMUserAddressSpace::kMaxInitialRandomize = 0x2000000ul;
+#endif
+
+
/*! Verifies that an area with the given aligned base and size fits into
the spot defined by base and limit and checks for overflows.
*/
@@ -40,6 +49,26 @@ is_valid_spot(addr_t base, addr_t alignedBase, addr_t size,
addr_t limit)
}
+/* http://graphics.stanford.edu/~seander/bithacks.html */
+static inline int
+log2(uint32_t v)
+{
+ static const int multiply_debruijn_bit_position[32] =
+ {
+ 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
+ 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
+ };
+
+ v |= v >> 1;
+ v |= v >> 2;
+ v |= v >> 4;
+ v |= v >> 8;
+ v |= v >> 16;
+
+ return multiply_debruijn_bit_position[(uint32_t)(v * 0x07c4acddu) >>
27];
+}
+
+
VMUserAddressSpace::VMUserAddressSpace(team_id id, addr_t base, size_t size)
:
VMAddressSpace(id, base, size, "address space"),
@@ -137,6 +166,7 @@ VMUserAddressSpace::InsertArea(VMArea* _area, size_t size,
break;
case B_BASE_ADDRESS:
+ case B_RANDOMIZED_BASE_ADDRESS:
searchBase = (addr_t)addressRestrictions->address;
searchEnd = fEndAddress;
break;
@@ -371,6 +401,41 @@ VMUserAddressSpace::Dump() const
}
+addr_t
+VMUserAddressSpace::_RandomizeAddress(addr_t start, addr_t end, bool initial)
+{
+ if (start == end)
+ return start;
+
+ const int kRandShift = log2(RAND_MAX) + 1;
+ int shift = 0;
+#ifdef B_HAIKU_64_BIT
+ uint64_t random = 0;
+ while (shift < 64) {
+ random |= (uint64_t)rand() << shift;
+ shift += kRandShift;
+ }
+#else
+ uint32_t random = 0;
+ while (shift < 32) {
+ random |= (uint32_t)rand() << shift;
+ shift += kRandShift;
+ }
+#endif
+
+ addr_t range = end - start;
+ if (initial)
+ range = min_c(range, kMaxInitialRandomize);
+ else
+ range = min_c(range, kMaxRandomize);
+
+ random %= range;
+ random &= ~addr_t(B_PAGE_SIZE - 1);
+
+ return start + random;
+}
+
+
/*! Finds a reserved area that covers the region spanned by \a start and
\a size, inserts the \a area into that region and makes sure that
there are reserved regions for the remaining parts.
@@ -459,6 +524,7 @@ VMUserAddressSpace::_InsertAreaSlot(addr_t start, addr_t
size, addr_t end,
VMUserArea* last = NULL;
VMUserArea* next;
bool foundSpot = false;
+ addr_t originalStart = 0;
TRACE(("VMUserAddressSpace::_InsertAreaSlot: address space %p, start "
"0x%lx, size %ld, end 0x%lx, addressSpec %" B_PRIu32 ", area
%p\n",
@@ -489,6 +555,11 @@ VMUserAddressSpace::_InsertAreaSlot(addr_t start, addr_t
size, addr_t end,
alignment <<= 1;
}
+ if (addressSpec == B_RANDOMIZED_BASE_ADDRESS) {
+ originalStart = start;
+ start = _RandomizeAddress(start, end - size, true);
+ }
+
start = ROUNDUP(start, alignment);
// walk up to the spot where we should start searching
@@ -614,6 +685,7 @@ second_chance:
}
case B_BASE_ADDRESS:
+ case B_RANDOMIZED_BASE_ADDRESS:
{
// find a hole big enough for a new area beginning with
"start"
if (last == NULL) {
@@ -646,15 +718,33 @@ second_chance:
foundSpot = true;
if (lastEnd < start)
area->SetBase(start);
- else
- area->SetBase(lastEnd + 1);
+ else {
+ start = lastEnd + 1;
+ if (addressSpec ==
B_RANDOMIZED_BASE_ADDRESS) {
+ addr_t spaceEnd = end;
+ if (next != NULL)
+ spaceEnd = next->Base();
+
+ start =
_RandomizeAddress(lastEnd + 1, spaceEnd - size,
+ false);
+ }
+
+ area->SetBase(start);
+ }
break;
}
// we didn't find a free spot in the requested range,
so we'll
// try again without any restrictions
- start = fBase;
- addressSpec = B_ANY_ADDRESS;
+ if (addressSpec != B_RANDOMIZED_BASE_ADDRESS
+ || originalStart == 0) {
+ start = fBase;
+ addressSpec = B_ANY_ADDRESS;
+ } else {
+ start = originalStart;
+ originalStart = 0;
+ }
+
last = NULL;
goto second_chance;
}
diff --git a/src/system/kernel/vm/VMUserAddressSpace.h
b/src/system/kernel/vm/VMUserAddressSpace.h
index fe5d37c..d24dc61 100644
--- a/src/system/kernel/vm/VMUserAddressSpace.h
+++ b/src/system/kernel/vm/VMUserAddressSpace.h
@@ -53,6 +53,9 @@ public:
virtual void Dump() const;
private:
+ static addr_t _RandomizeAddress(addr_t start,
addr_t end,
+ bool
initial);
+
status_t
_InsertAreaIntoReservedRegion(addr_t start,
size_t
size, VMUserArea* area,
uint32
allocationFlags);
@@ -62,6 +65,9 @@ private:
uint32
allocationFlags);
private:
+ static const addr_t kMaxRandomize;
+ static const addr_t kMaxInitialRandomize;
+
VMUserAreaList fAreas;
mutable VMUserArea* fAreaHint;
};
diff --git a/src/system/kernel/vm/vm.cpp b/src/system/kernel/vm/vm.cpp
index 6e809b6..3503b2b 100644
--- a/src/system/kernel/vm/vm.cpp
+++ b/src/system/kernel/vm/vm.cpp
@@ -1219,6 +1219,7 @@ vm_create_anonymous_area(team_id team, const char *name,
addr_t size,
case B_BASE_ADDRESS:
case B_ANY_KERNEL_ADDRESS:
case B_ANY_KERNEL_BLOCK_ADDRESS:
+ case B_RANDOMIZED_BASE_ADDRESS:
break;
default:
############################################################################
Commit: 7547e2596e8c89c28c4c2bde263ca132bbe61f31
Author: Pawel Dziepak <pdziepak@xxxxxxxxxxx>
Date: Wed Feb 27 00:32:09 2013 UTC
vm: implement B_RANDOMIZED_ANY_ADDRESS address specification
Randomized equivalent of B_ANY_ADDRESS. When a free space is found (as in
B_ANY_ADDRESS) the base adress is then randomized using _RandomizeAddress
pretty much like it is done in B_RANDOMIZED_BASE_ADDRESS.
----------------------------------------------------------------------------
diff --git a/headers/os/kernel/OS.h b/headers/os/kernel/OS.h
index e65dc1b..eac7b7b 100644
--- a/headers/os/kernel/OS.h
+++ b/headers/os/kernel/OS.h
@@ -79,7 +79,7 @@ typedef struct area_info {
#define B_CLONE_ADDRESS 3
#define B_ANY_KERNEL_ADDRESS 4
/* B_ANY_KERNEL_BLOCK_ADDRESS 5 */
-/* B_RANDOMIZED_ANY_ADDRESS 6 */
+#define B_RANDOMIZED_ANY_ADDRESS 6
#define B_RANDOMIZED_BASE_ADDRESS 7
/* area protection */
diff --git a/src/system/kernel/vm/VMUserAddressSpace.cpp
b/src/system/kernel/vm/VMUserAddressSpace.cpp
index 8e45bec..1933eb6 100644
--- a/src/system/kernel/vm/VMUserAddressSpace.cpp
+++ b/src/system/kernel/vm/VMUserAddressSpace.cpp
@@ -174,6 +174,7 @@ VMUserAddressSpace::InsertArea(VMArea* _area, size_t size,
case B_ANY_ADDRESS:
case B_ANY_KERNEL_ADDRESS:
case B_ANY_KERNEL_BLOCK_ADDRESS:
+ case B_RANDOMIZED_ANY_ADDRESS:
searchBase = fBase;
// TODO: remove this again when vm86 mode is moved into
the kernel
// completely (currently needs a userland address
space!)
@@ -402,8 +403,11 @@ VMUserAddressSpace::Dump() const
addr_t
-VMUserAddressSpace::_RandomizeAddress(addr_t start, addr_t end, bool initial)
+VMUserAddressSpace::_RandomizeAddress(addr_t start, addr_t end,
+ size_t alignment, bool initial)
{
+ ASSERT((start & addr_t(alignment - 1)) == 0);
+
if (start == end)
return start;
@@ -430,7 +434,7 @@ VMUserAddressSpace::_RandomizeAddress(addr_t start, addr_t
end, bool initial)
range = min_c(range, kMaxRandomize);
random %= range;
- random &= ~addr_t(B_PAGE_SIZE - 1);
+ random &= ~addr_t(alignment - 1);
return start + random;
}
@@ -555,13 +559,13 @@ VMUserAddressSpace::_InsertAreaSlot(addr_t start, addr_t
size, addr_t end,
alignment <<= 1;
}
+ start = ROUNDUP(start, alignment);
+
if (addressSpec == B_RANDOMIZED_BASE_ADDRESS) {
originalStart = start;
- start = _RandomizeAddress(start, end - size, true);
+ start = _RandomizeAddress(start, end - size, alignment, true);
}
-
- start = ROUNDUP(start, alignment);
-
+
// walk up to the spot where we should start searching
second_chance:
VMUserAreaList::Iterator it = fAreas.GetIterator();
@@ -581,13 +585,20 @@ second_chance:
case B_ANY_ADDRESS:
case B_ANY_KERNEL_ADDRESS:
case B_ANY_KERNEL_BLOCK_ADDRESS:
+ case B_RANDOMIZED_ANY_ADDRESS:
{
// find a hole big enough for a new area
if (last == NULL) {
// see if we can build it at the beginning of
the virtual map
addr_t alignedBase = ROUNDUP(start, alignment);
- if (is_valid_spot(start, alignedBase, size,
- next == NULL ? end :
next->Base())) {
+ addr_t nextBase = next == NULL ? end :
next->Base();
+ if (is_valid_spot(start, alignedBase, size,
nextBase)) {
+
+ if (addressSpec ==
B_RANDOMIZED_ANY_ADDRESS) {
+ alignedBase =
_RandomizeAddress(alignedBase,
+ nextBase - size,
alignment);
+ }
+
foundSpot = true;
area->SetBase(alignedBase);
break;
@@ -603,6 +614,12 @@ second_chance:
alignment);
if (is_valid_spot(last->Base() + (last->Size()
- 1),
alignedBase, size,
next->Base())) {
+
+ if (addressSpec ==
B_RANDOMIZED_ANY_ADDRESS) {
+ alignedBase =
_RandomizeAddress(alignedBase,
+ next->Base() - size,
alignment);
+ }
+
foundSpot = true;
area->SetBase(alignedBase);
break;
@@ -619,6 +636,12 @@ second_chance:
alignment);
if (is_valid_spot(last->Base() + (last->Size() - 1),
alignedBase,
size, end)) {
+
+ if (addressSpec == B_RANDOMIZED_ANY_ADDRESS) {
+ alignedBase =
_RandomizeAddress(alignedBase, end - size,
+ alignment);
+ }
+
// got a spot
foundSpot = true;
area->SetBase(alignedBase);
@@ -653,12 +676,19 @@ second_chance:
if ((next->protection &
RESERVED_AVOID_BASE) == 0
&& alignedBase == next->Base()
&& next->Size() >= size) {
+
+ if (addressSpec ==
B_RANDOMIZED_ANY_ADDRESS) {
+ alignedBase =
_RandomizeAddress(next->Base(),
+ next->Size() -
size, alignment);
+ }
+ addr_t offset = alignedBase -
next->Base();
+
// The new area will be placed
at the beginning of the
// reserved area and the
reserved area will be offset
// and resized
foundSpot = true;
- next->SetBase(next->Base() +
size);
- next->SetSize(next->Size() -
size);
+ next->SetBase(next->Base() +
offset + size);
+ next->SetSize(next->Size() -
offset - size);
area->SetBase(alignedBase);
break;
}
@@ -668,8 +698,23 @@ second_chance:
// The new area will be placed
at the end of the
// reserved area, and the
reserved area will be resized
// to make space
- alignedBase = ROUNDDOWN(
- next->Base() +
next->Size() - size, alignment);
+
+ if (addressSpec ==
B_RANDOMIZED_ANY_ADDRESS) {
+ addr_t alignedNextBase
= ROUNDUP(next->Base(),
+ alignment);
+
+ addr_t startRange =
next->Base() + next->Size();
+ startRange -= size +
kMaxRandomize;
+ startRange =
ROUNDDOWN(startRange, alignment);
+
+ startRange =
max_c(startRange, alignedNextBase);
+
+ alignedBase =
_RandomizeAddress(startRange,
+ next->Base() +
next->Size() - size, alignment);
+ } else {
+ alignedBase = ROUNDDOWN(
+ next->Base() +
next->Size() - size, alignment);
+ }
foundSpot = true;
next->SetSize(alignedBase -
next->Base());
@@ -726,7 +771,7 @@ second_chance:
spaceEnd = next->Base();
start =
_RandomizeAddress(lastEnd + 1, spaceEnd - size,
- false);
+ B_PAGE_SIZE);
}
area->SetBase(start);
@@ -736,10 +781,12 @@ second_chance:
// we didn't find a free spot in the requested range,
so we'll
// try again without any restrictions
- if (addressSpec != B_RANDOMIZED_BASE_ADDRESS
- || originalStart == 0) {
+ if (addressSpec != B_RANDOMIZED_BASE_ADDRESS) {
start = fBase;
addressSpec = B_ANY_ADDRESS;
+ } else if (originalStart == 0) {
+ start = fBase;
+ addressSpec = B_RANDOMIZED_ANY_ADDRESS;
} else {
start = originalStart;
originalStart = 0;
diff --git a/src/system/kernel/vm/VMUserAddressSpace.h
b/src/system/kernel/vm/VMUserAddressSpace.h
index d24dc61..0aa4261 100644
--- a/src/system/kernel/vm/VMUserAddressSpace.h
+++ b/src/system/kernel/vm/VMUserAddressSpace.h
@@ -54,7 +54,7 @@ public:
private:
static addr_t _RandomizeAddress(addr_t start,
addr_t end,
- bool
initial);
+ size_t
alignment, bool initial = false);
status_t
_InsertAreaIntoReservedRegion(addr_t start,
size_t
size, VMUserArea* area,
diff --git a/src/system/kernel/vm/vm.cpp b/src/system/kernel/vm/vm.cpp
index 3503b2b..fb6c246 100644
--- a/src/system/kernel/vm/vm.cpp
+++ b/src/system/kernel/vm/vm.cpp
@@ -1219,6 +1219,7 @@ vm_create_anonymous_area(team_id team, const char *name,
addr_t size,
case B_BASE_ADDRESS:
case B_ANY_KERNEL_ADDRESS:
case B_ANY_KERNEL_BLOCK_ADDRESS:
+ case B_RANDOMIZED_ANY_ADDRESS:
case B_RANDOMIZED_BASE_ADDRESS:
break;
Other related posts: