> This patch adds a new module 'ssfmalloc', a "simple and straight-forward
> memory
> allocation" facility.
This sets of patches fixes portability issues and does small improvements.
2020-10-25 Bruno Haible <br...@clisp.org>
ssfmalloc tests: Small tweaks.
* tests/test-ssfmalloc.c: Add comments.
(alloc_pages): Don't require PROT_EXEC bits.
(block_sizes): Add more small sizes, for better coverage of
ssfmalloc-bitmap.h.
ssfmalloc tests: Portability to Minix.
* modules/ssfmalloc-tests (Files): Add m4/mmap-anon.m4.
(configure.ac): Invoke gl_FUNC_MMAP_ANON.
* m4/mmap-anon.m4: Update comment.
ssfmalloc: Portability to AIX.
* modules/ssfmalloc (Include): Add ssfmalloc.h.
(Link): New section.
* modules/ssfmalloc-tests (Makefile.am): Link test-ssfmalloc with
$(LIBTHREAD).
ssfmalloc: Portability to Cygwin.
* lib/ssfmalloc.h: Add parameter PAGESIZE_MAX.
(pg_offset_t): Define depending on PAGESIZE_MAX.
* tests/test-ssfmalloc.c: Undefine PAGESIZE.
(PAGESIZE_MAX): New macro.
ssfmalloc: Fix buffer overrun in bitmap search.
* lib/ssfmalloc-bitmap.h (find_first_packet_set): Don't access the
word *words_end.
From c433211e54786e26b9c787f3d4a4212536ffaa46 Mon Sep 17 00:00:00 2001
From: Bruno Haible <br...@clisp.org>
Date: Sun, 25 Oct 2020 18:03:34 +0100
Subject: [PATCH 1/5] ssfmalloc: Fix buffer overrun in bitmap search.
* lib/ssfmalloc-bitmap.h (find_first_packet_set): Don't access the
word *words_end.
---
ChangeLog | 6 ++
lib/ssfmalloc-bitmap.h | 248 ++++++++++++++++++++++++-------------------------
2 files changed, 130 insertions(+), 124 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index 8fa32e1..ed0195d 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,9 @@
+2020-10-25 Bruno Haible <br...@clisp.org>
+
+ ssfmalloc: Fix buffer overrun in bitmap search.
+ * lib/ssfmalloc-bitmap.h (find_first_packet_set): Don't access the
+ word *words_end.
+
2020-10-24 Paul Eggert <egg...@cs.ucla.edu>
doc: mention ‘restrict’ and C++
diff --git a/lib/ssfmalloc-bitmap.h b/lib/ssfmalloc-bitmap.h
index abf9949..7410675 100644
--- a/lib/ssfmalloc-bitmap.h
+++ b/lib/ssfmalloc-bitmap.h
@@ -92,217 +92,217 @@ find_first_packet_set (size_t num_words, const uint32_t *words, size_t c)
}
case 2:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t combined = longword & (longword >> 1);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 3:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t combined = longword & (longword >> 1) & (longword >> 2);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 4:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t combined = tmp1 & (tmp1 >> 2);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 5:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t combined = tmp2 & (longword >> 4);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 6:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t combined = tmp1 & (tmp1 >> 2) & (tmp1 >> 4);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 7:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t combined =
tmp1 & (tmp1 >> 2) & (tmp1 >> 4) & (longword >> 6);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 8:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t combined = tmp2 & (tmp2 >> 4);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 9:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t tmp3 = tmp2 & (tmp2 >> 4);
uint64_t combined = tmp3 & (longword >> 8);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 10:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t tmp3 = tmp2 & (tmp2 >> 4);
uint64_t combined = tmp3 & (tmp1 >> 8);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 11:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t tmp3 = tmp2 & (tmp2 >> 4);
uint64_t combined = tmp3 & (tmp1 >> 8) & (longword >> 10);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 12:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t combined = tmp2 & (tmp2 >> 4) & (tmp2 >> 8);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 13:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t combined =
tmp2 & (tmp2 >> 4) & (tmp2 >> 8) & (longword >> 12);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 14:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t combined = tmp2 & (tmp2 >> 4) & (tmp2 >> 8) & (tmp1 >> 12);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 15:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
/* Optimized: Use 5, not 6, '&' operations. */
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
@@ -310,34 +310,34 @@ find_first_packet_set (size_t num_words, const uint32_t *words, size_t c)
uint64_t combined = tmp3 & (tmp3 >> 5) & (tmp3 >> 10);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 16:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t tmp3 = tmp2 & (tmp2 >> 4);
uint64_t combined = tmp3 & (tmp3 >> 8);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 17:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t tmp3 = tmp2 & (tmp2 >> 4);
@@ -345,17 +345,17 @@ find_first_packet_set (size_t num_words, const uint32_t *words, size_t c)
uint64_t combined = tmp4 & (longword >> 16);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 18:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t tmp3 = tmp2 & (tmp2 >> 4);
@@ -363,17 +363,17 @@ find_first_packet_set (size_t num_words, const uint32_t *words, size_t c)
uint64_t combined = tmp4 & (tmp1 >> 16);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 19:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t tmp3 = tmp2 & (tmp2 >> 4);
@@ -381,17 +381,17 @@ find_first_packet_set (size_t num_words, const uint32_t *words, size_t c)
uint64_t combined = tmp4 & (tmp1 >> 16) & (longword >> 18);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 20:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t tmp3 = tmp2 & (tmp2 >> 4);
@@ -399,17 +399,17 @@ find_first_packet_set (size_t num_words, const uint32_t *words, size_t c)
uint64_t combined = tmp4 & (tmp2 >> 16);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 21:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t tmp3 = tmp2 & (tmp2 >> 4);
@@ -417,17 +417,17 @@ find_first_packet_set (size_t num_words, const uint32_t *words, size_t c)
uint64_t combined = tmp4 & (tmp2 >> 16) & (longword >> 20);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 22:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t tmp3 = tmp2 & (tmp2 >> 4);
@@ -435,17 +435,17 @@ find_first_packet_set (size_t num_words, const uint32_t *words, size_t c)
uint64_t combined = tmp4 & (tmp2 >> 16) & (tmp1 >> 20);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 23:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t tmp3 = tmp2 & (tmp2 >> 4);
@@ -454,34 +454,34 @@ find_first_packet_set (size_t num_words, const uint32_t *words, size_t c)
tmp4 & (tmp2 >> 16) & (tmp1 >> 20) & (longword >> 22);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 24:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t tmp3 = tmp2 & (tmp2 >> 4);
uint64_t combined = tmp3 & (tmp3 >> 8) & (tmp3 >> 16);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 25:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t tmp3 = tmp2 & (tmp2 >> 4);
@@ -489,17 +489,17 @@ find_first_packet_set (size_t num_words, const uint32_t *words, size_t c)
tmp3 & (tmp3 >> 8) & (tmp3 >> 16) & (longword >> 24);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 26:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t tmp3 = tmp2 & (tmp2 >> 4);
@@ -507,17 +507,17 @@ find_first_packet_set (size_t num_words, const uint32_t *words, size_t c)
tmp3 & (tmp3 >> 8) & (tmp3 >> 16) & (tmp1 >> 24);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 27:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
/* Optimized: Use 6, not 7, '&' operations. */
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
@@ -526,17 +526,17 @@ find_first_packet_set (size_t num_words, const uint32_t *words, size_t c)
uint64_t combined = tmp4 & (tmp4 >> 9) & (tmp4 >> 18);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 28:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t tmp3 = tmp2 & (tmp2 >> 4);
@@ -544,17 +544,17 @@ find_first_packet_set (size_t num_words, const uint32_t *words, size_t c)
tmp3 & (tmp3 >> 8) & (tmp3 >> 16) & (tmp2 >> 24);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 29:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t tmp3 = tmp2 & (tmp2 >> 4);
@@ -562,17 +562,17 @@ find_first_packet_set (size_t num_words, const uint32_t *words, size_t c)
tmp3 & (tmp3 >> 8) & (tmp3 >> 16) & (tmp2 >> 24) & (longword >> 28);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 30:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
/* Optimized: Use 6, not 7, '&' operations. */
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
@@ -581,17 +581,17 @@ find_first_packet_set (size_t num_words, const uint32_t *words, size_t c)
uint64_t combined = tmp4 & (tmp4 >> 10) & (tmp4 >> 20);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 31:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t tmp3 = tmp2 & (tmp2 >> 4);
@@ -600,17 +600,17 @@ find_first_packet_set (size_t num_words, const uint32_t *words, size_t c)
tmp4 & (tmp3 >> 16) & (tmp2 >> 24) & (tmp1 >> 28) & (longword >> 30);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
case 32:
{
- for (; ptr < words_end; ptr++)
+ while (ptr < words_end)
{
- uint64_t longword = ptr[0];
+ uint64_t longword = *ptr++;
if (likely (ptr < words_end))
- longword |= ((uint64_t) ptr[1]) << 32;
+ longword |= ((uint64_t) *ptr) << 32;
uint64_t tmp1 = longword & (longword >> 1);
uint64_t tmp2 = tmp1 & (tmp1 >> 2);
uint64_t tmp3 = tmp2 & (tmp2 >> 4);
@@ -618,7 +618,7 @@ find_first_packet_set (size_t num_words, const uint32_t *words, size_t c)
uint64_t combined = tmp4 & (tmp4 >> 16);
size_t found = ffsll (combined);
if (found > 0)
- return 32 * (ptr - words) + (found - 1);
+ return 32 * (ptr - 1 - words) + (found - 1);
}
return (size_t)(-1);
}
--
2.7.4
>From 476f69f3bf87887c61f938e6450da874826df867 Mon Sep 17 00:00:00 2001
From: Bruno Haible <br...@clisp.org>
Date: Sun, 25 Oct 2020 18:08:44 +0100
Subject: [PATCH 2/5] ssfmalloc: Portability to Cygwin.
* lib/ssfmalloc.h: Add parameter PAGESIZE_MAX.
(pg_offset_t): Define depending on PAGESIZE_MAX.
* tests/test-ssfmalloc.c: Undefine PAGESIZE.
(PAGESIZE_MAX): New macro.
---
ChangeLog | 6 ++++++
lib/ssfmalloc.h | 6 ++++++
tests/test-ssfmalloc.c | 12 ++++++++++++
3 files changed, 24 insertions(+)
diff --git a/ChangeLog b/ChangeLog
index ed0195d..5f82793 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
2020-10-25 Bruno Haible <br...@clisp.org>
+ ssfmalloc: Portability to Cygwin.
+ * lib/ssfmalloc.h: Add parameter PAGESIZE_MAX.
+ (pg_offset_t): Define depending on PAGESIZE_MAX.
+ * tests/test-ssfmalloc.c: Undefine PAGESIZE.
+ (PAGESIZE_MAX): New macro.
+
ssfmalloc: Fix buffer overrun in bitmap search.
* lib/ssfmalloc-bitmap.h (find_first_packet_set): Don't access the
word *words_end.
diff --git a/lib/ssfmalloc.h b/lib/ssfmalloc.h
index 999126e..43d0851 100644
--- a/lib/ssfmalloc.h
+++ b/lib/ssfmalloc.h
@@ -55,6 +55,8 @@
PAGESIZE A variable-like macro of type intptr_t or uintptr_t
that evaluates to the memory page size (>= 4096).
+ PAGESIZE_MAX A constant that specifies an upper bound for PAGESIZE.
+
ALLOC_PAGES A function-like macro with the signature
uintptr_t ALLOC_PAGES (size_t size)
where the argument size is > 0 and a multiple of the
@@ -151,7 +153,11 @@ struct any_page_header
/* ========================= Small and medium blocks ======================== */
/* An integer type, capable of holding the values 0 .. PAGESIZE. */
+#if PAGESIZE_MAX >= 0x10000
+typedef unsigned int pg_offset_t;
+#else
typedef unsigned short pg_offset_t;
+#endif
/* Tree element that corresponds to a page.
These tree elements are allocated via malloc(). */
diff --git a/tests/test-ssfmalloc.c b/tests/test-ssfmalloc.c
index e1dfcec..09427c7 100644
--- a/tests/test-ssfmalloc.c
+++ b/tests/test-ssfmalloc.c
@@ -118,13 +118,25 @@ free_pages (uintptr_t pages, size_t size)
#endif
}
+/* Cygwin defines PAGESIZE in <limits.h>. */
+#undef PAGESIZE
+
/* ======================= Instantiate the front end ======================= */
#define PAGESIZE pagesize
+/* On Cygwin, PAGESIZE is 65536. On all other platforms, it is either 4096
+ or 8192. */
+#ifdef __CYGWIN__
+# define PAGESIZE_MAX 65536
+#else
+# define PAGESIZE_MAX 8192
+#endif
+
#define ALLOC_PAGES alloc_pages
#define FREE_PAGES free_pages
#define ALIGNMENT (sizeof (void *)) /* or 8 or 16 or 32 */
#define PAGE_RESERVED_HEADER_SIZE (3 * UINTPTR_WIDTH / 8) /* = 3 * sizeof (void *) */
+
#include "ssfmalloc.h"
/* ================================= Tests ================================= */
--
2.7.4
>From 92e34aba7c512f4084fa2447087d090be554c0e0 Mon Sep 17 00:00:00 2001
From: Bruno Haible <br...@clisp.org>
Date: Sun, 25 Oct 2020 18:14:09 +0100
Subject: [PATCH 3/5] ssfmalloc: Portability to AIX.
* modules/ssfmalloc (Include): Add ssfmalloc.h.
(Link): New section.
* modules/ssfmalloc-tests (Makefile.am): Link test-ssfmalloc with
$(LIBTHREAD).
---
ChangeLog | 6 ++++++
modules/ssfmalloc | 4 ++++
modules/ssfmalloc-tests | 1 +
3 files changed, 11 insertions(+)
diff --git a/ChangeLog b/ChangeLog
index 5f82793..32b5e0e 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
2020-10-25 Bruno Haible <br...@clisp.org>
+ ssfmalloc: Portability to AIX.
+ * modules/ssfmalloc (Include): Add ssfmalloc.h.
+ (Link): New section.
+ * modules/ssfmalloc-tests (Makefile.am): Link test-ssfmalloc with
+ $(LIBTHREAD).
+
ssfmalloc: Portability to Cygwin.
* lib/ssfmalloc.h: Add parameter PAGESIZE_MAX.
(pg_offset_t): Define depending on PAGESIZE_MAX.
diff --git a/modules/ssfmalloc b/modules/ssfmalloc
index d46f652..ace411b 100644
--- a/modules/ssfmalloc
+++ b/modules/ssfmalloc
@@ -19,6 +19,10 @@ configure.ac:
Makefile.am:
Include:
+"ssfmalloc.h"
+
+Link:
+$(LIBTHREAD)
License:
LGPLv2+
diff --git a/modules/ssfmalloc-tests b/modules/ssfmalloc-tests
index ea1ed2c..c1994f1 100644
--- a/modules/ssfmalloc-tests
+++ b/modules/ssfmalloc-tests
@@ -9,3 +9,4 @@ configure.ac:
Makefile.am:
TESTS += test-ssfmalloc
check_PROGRAMS += test-ssfmalloc
+test_ssfmalloc_LDADD = $(LDADD) $(LIBTHREAD)
--
2.7.4
>From 4b52185214e9bd28026df2e1694191f2f8abe3f1 Mon Sep 17 00:00:00 2001
From: Bruno Haible <br...@clisp.org>
Date: Sun, 25 Oct 2020 18:16:10 +0100
Subject: [PATCH 4/5] ssfmalloc tests: Portability to Minix.
* modules/ssfmalloc-tests (Files): Add m4/mmap-anon.m4.
(configure.ac): Invoke gl_FUNC_MMAP_ANON.
* m4/mmap-anon.m4: Update comment.
---
ChangeLog | 5 +++++
m4/mmap-anon.m4 | 4 ++--
modules/ssfmalloc-tests | 2 ++
3 files changed, 9 insertions(+), 2 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index 32b5e0e..26ba40c 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,10 @@
2020-10-25 Bruno Haible <br...@clisp.org>
+ ssfmalloc tests: Portability to Minix.
+ * modules/ssfmalloc-tests (Files): Add m4/mmap-anon.m4.
+ (configure.ac): Invoke gl_FUNC_MMAP_ANON.
+ * m4/mmap-anon.m4: Update comment.
+
ssfmalloc: Portability to AIX.
* modules/ssfmalloc (Include): Add ssfmalloc.h.
(Link): New section.
diff --git a/m4/mmap-anon.m4 b/m4/mmap-anon.m4
index d5c69df..2995ad5 100644
--- a/m4/mmap-anon.m4
+++ b/m4/mmap-anon.m4
@@ -1,4 +1,4 @@
-# mmap-anon.m4 serial 10
+# mmap-anon.m4 serial 11
dnl Copyright (C) 2005, 2007, 2009-2020 Free Software Foundation, Inc.
dnl This file is free software; the Free Software Foundation
dnl gives unlimited permission to copy and/or distribute it,
@@ -9,7 +9,7 @@ dnl with or without modifications, as long as this notice is preserved.
# - On Linux, AIX, OSF/1, Solaris, Cygwin, Interix, Haiku, both MAP_ANONYMOUS
# and MAP_ANON exist and have the same value.
# - On HP-UX, only MAP_ANONYMOUS exists.
-# - On Mac OS X, FreeBSD, NetBSD, OpenBSD, only MAP_ANON exists.
+# - On Mac OS X, FreeBSD, NetBSD, OpenBSD, Minix, only MAP_ANON exists.
# - On IRIX, neither exists, and a file descriptor opened to /dev/zero must be
# used.
diff --git a/modules/ssfmalloc-tests b/modules/ssfmalloc-tests
index c1994f1..5e35fe4 100644
--- a/modules/ssfmalloc-tests
+++ b/modules/ssfmalloc-tests
@@ -1,10 +1,12 @@
Files:
tests/test-ssfmalloc.c
tests/macros.h
+m4/mmap-anon.m4
Depends-on:
configure.ac:
+gl_FUNC_MMAP_ANON
Makefile.am:
TESTS += test-ssfmalloc
--
2.7.4
>From 475eac69463f384419a3b5a8bd449a6876123fab Mon Sep 17 00:00:00 2001
From: Bruno Haible <br...@clisp.org>
Date: Sun, 25 Oct 2020 18:18:06 +0100
Subject: [PATCH 5/5] ssfmalloc tests: Small tweaks.
* tests/test-ssfmalloc.c: Add comments.
(alloc_pages): Don't require PROT_EXEC bits.
(block_sizes): Add more small sizes, for better coverage of
ssfmalloc-bitmap.h.
---
ChangeLog | 6 ++++++
tests/test-ssfmalloc.c | 25 ++++++++++++++++++++++++-
2 files changed, 30 insertions(+), 1 deletion(-)
diff --git a/ChangeLog b/ChangeLog
index 26ba40c..bb838bc 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
2020-10-25 Bruno Haible <br...@clisp.org>
+ ssfmalloc tests: Small tweaks.
+ * tests/test-ssfmalloc.c: Add comments.
+ (alloc_pages): Don't require PROT_EXEC bits.
+ (block_sizes): Add more small sizes, for better coverage of
+ ssfmalloc-bitmap.h.
+
ssfmalloc tests: Portability to Minix.
* modules/ssfmalloc-tests (Files): Add m4/mmap-anon.m4.
(configure.ac): Invoke gl_FUNC_MMAP_ANON.
diff --git a/tests/test-ssfmalloc.c b/tests/test-ssfmalloc.c
index 09427c7..9699e6b 100644
--- a/tests/test-ssfmalloc.c
+++ b/tests/test-ssfmalloc.c
@@ -92,7 +92,7 @@ alloc_pages (size_t size)
return (uintptr_t) mem;
#else
/* Use mmap with the MAP_ANONYMOUS or MAP_ANON flag. */
- void *mem = mmap (NULL, size, PROT_READ | PROT_WRITE | PROT_EXEC,
+ void *mem = mmap (NULL, size, PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS | MAP_VARIABLE, -1, 0);
if (mem == (void *)(-1))
return 0;
@@ -143,6 +143,7 @@ free_pages (uintptr_t pages, size_t size)
#include "macros.h"
+/* Fills a block of a given size with some contents. */
static void
fill_block (uintptr_t block, size_t size)
{
@@ -150,6 +151,8 @@ fill_block (uintptr_t block, size_t size)
memset ((char *) block, code, size);
}
+/* Verifies that the contents of a block is still present
+ (i.e. has not accidentally been overwritten by other operations). */
static void
verify_block (uintptr_t block, size_t size)
{
@@ -187,12 +190,29 @@ static size_t block_sizes[] =
64,
65,
71,
+ 77,
83,
+ 96,
99,
110,
+ 119,
127,
128,
+ 130,
+ 144,
+ 150,
+ 157,
+ 161,
169,
+ 180,
+ 192,
+ 199,
+ 204,
+ 210,
+ 224,
+ 225,
+ 236,
+ 241,
249,
255,
256,
@@ -266,6 +286,9 @@ main (int argc, char *argv[])
init_pagesize ();
+ /* Randomly allocate and deallocate blocks.
+ Also verify that there are no unexpected modifications to the contents of
+ these blocks. */
{
unsigned int repeat;
char *blocks[SIZEOF (block_sizes)];
--
2.7.4
