boringssl

History

David Benjamin aadcce380f Implement sk_find manually. glibc inlines bsearch, so CFI does observe the function pointer mishap. Binary search is easy enough, aside from thinking through the edge case at the end, so just implement it by hand. As a bonus, it actually gives O(lg N) behavior. sk__find needs to return the first* match, while bsearch does not promise a particular one. sk_find thus performs a fixup step to find the first one, but this is linear in the number of matching elements. Instead, the binary search should take this into account. This still leaves qsort, but it's not inlined, so hopefully we can leave it alone. Bug: chromium:941463 Change-Id: I5c94d6b15423beea3bdb389639466f8b3ff0dc5d Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/35304 Reviewed-by: Adam Langley <agl@google.com>	2019-03-14 15:21:48 +00:00
..
stack_test.cc	Fix stack_test.cc in the prefixed build.	2018-11-27 21:35:56 +00:00
stack.c	Implement sk_find manually.	2019-03-14 15:21:48 +00:00

David Benjamin aadcce380f Implement sk_find manually.

glibc inlines bsearch, so CFI does observe the function pointer mishap.
Binary search is easy enough, aside from thinking through the edge case
at the end, so just implement it by hand. As a bonus, it actually gives
O(lg N) behavior.

sk_*_find needs to return the *first* match, while bsearch does not
promise a particular one. sk_find thus performs a fixup step to find the
first one, but this is linear in the number of matching elements.
Instead, the binary search should take this into account.

This still leaves qsort, but it's not inlined, so hopefully we can leave
it alone.

Bug: chromium:941463
Change-Id: I5c94d6b15423beea3bdb389639466f8b3ff0dc5d
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/35304
Reviewed-by: Adam Langley <agl@google.com>

2019-03-14 15:21:48 +00:00

stack_test.cc

Fix stack_test.cc in the prefixed build.

2018-11-27 21:35:56 +00:00

stack.c

Implement sk_find manually.

2019-03-14 15:21:48 +00:00