aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorNeels Hofmeyr <neels@hofmeyr.de>2019-02-26 19:33:27 +0100
committerNeels Hofmeyr <neels@hofmeyr.de>2019-02-26 21:54:39 +0100
commitb75f5ae6df9919f0f55d05329810e4d0b6f06cce (patch)
tree842514a9c2fb12dac50ec115e49012de2472b5b2
parent014a6625e9a30d9b009b687278cae5be5c461e7f (diff)
add osmo_string_ringbuffer and osmo_static_string() API
-rw-r--r--include/osmocom/core/utils.h29
-rw-r--r--src/utils.c156
-rw-r--r--tests/utils/utils_test.c110
-rw-r--r--tests/utils/utils_test.ok344
4 files changed, 639 insertions, 0 deletions
diff --git a/include/osmocom/core/utils.h b/include/osmocom/core/utils.h
index 16159d3..efc9bcc 100644
--- a/include/osmocom/core/utils.h
+++ b/include/osmocom/core/utils.h
@@ -230,4 +230,33 @@ struct osmo_strbuf {
#define OSMO_STRBUF_PRINTF(STRBUF, fmt, args...) \
OSMO_STRBUF_APPEND(STRBUF, snprintf, fmt, ##args)
+/*! State for managing a ringbuffer of static strings. See osmo_static_string(). */
+struct osmo_string_ringbuffer {
+ /*! Start of the usable memory. */
+ char *buf;
+ /*! Size of the usable memory. */
+ size_t buf_size;
+ /*! Pointer to after the last used static string. */
+ char *next;
+ /*! Most recent usages, for sanity checking. If not NULL, should point to an array of char*[recent_len]. */
+ char **recent;
+ /*! Number of recent usages that is considered as still in use. */
+ size_t recent_len;
+};
+
+char *osmo_string_ringbuffer_get(struct osmo_string_ringbuffer *buf, size_t bufsize);
+size_t osmo_string_ringbuffer_avail(struct osmo_string_ringbuffer *buf);
+void osmo_string_ringbuffer_clear(struct osmo_string_ringbuffer *buf);
+
+char *osmo_static_string(size_t bufsize);
+
+/*! Useful to pass osmo_static_string() and size arguments without repeating the size.
+ *
+ * printf("%s\n", osmo_hexdump_buf(OSMO_STATIC_STRING(my_data_len*2), my_data, my_data_len, NULL, false));
+ */
+#define OSMO_STATIC_STRING(SIZE) osmo_static_string(SIZE), (SIZE)
+
+extern struct osmo_string_ringbuffer osmo_static_string_buf_default;
+extern struct osmo_string_ringbuffer *osmo_static_string_buf;
+
/*! @} */
diff --git a/src/utils.c b/src/utils.c
index 2d5bcb0..12189b6 100644
--- a/src/utils.c
+++ b/src/utils.c
@@ -826,4 +826,160 @@ const char osmo_luhn(const char* in, int in_len)
return (sum * 9) % 10 + '0';
}
+/*! Return section from a string ringbuffer that is currently considered unused.
+ * \param[in] buf osmo_string_ringbuffer instance.
+ * \param[in] bufsize The amount of bytes that should be available, caller needs to include terminating nul.
+ * \returns Pointer to string buffer, or NULL if there is not enough unused memory available in osmo_static_string_buf.
+ */
+char *osmo_string_ringbuffer_get(struct osmo_string_ringbuffer *buf, size_t bufsize)
+{
+ char *ret;
+ int i;
+
+ if (!bufsize || !buf)
+ return NULL;
+
+ if (bufsize > buf->buf_size)
+ return NULL;
+
+ ret = buf->next;
+ if (ret < buf->buf
+ || ret + bufsize > buf->buf + buf->buf_size)
+ ret = buf->buf;
+
+ if (buf->recent) {
+ if (ret <= buf->recent[0]
+ && bufsize > buf->recent[0] - ret)
+ return NULL;
+
+ /* Record used chunk in list of recent buffers */
+ for (i = 0; i < buf->recent_len; i++) {
+ if (!buf->recent[i])
+ break;
+ }
+
+ if (i < buf->recent_len)
+ buf->recent[i] = ret;
+ else {
+ if (buf->recent_len > 1)
+ memmove(&buf->recent[0], &buf->recent[1], (buf->recent_len - 1) *
+ sizeof(buf->recent[0]));
+ buf->recent[buf->recent_len - 1] = ret;
+ }
+ }
+
+ buf->next = ret + bufsize;
+
+ return ret;
+}
+
+/*! Reset string ringbuffer to make all of its space available.
+ * This can be useful to mark a buffer as unused, e.g. to recover from a full buffer, or before and after the caller
+ * would like to allocate an unusually large buffer. All previously allocated pointers gotten by
+ * osmo_string_ringbuffer_get() for this ring buffer must no longer be used. */
+void osmo_string_ringbuffer_clear(struct osmo_string_ringbuffer *buf)
+{
+ if (buf->recent && buf->recent_len)
+ memset(buf->recent, 0, buf->recent_len * sizeof(buf->recent[0]));
+ buf->next = NULL;
+}
+
+/*! Return the largest amount of bytes that could be allocated at this point in time.
+ * \param[in] buf osmo_string_ringbuffer instance.
+ * \returns Size of largest continuous chunk of bytes available.
+ */
+size_t osmo_string_ringbuffer_avail(struct osmo_string_ringbuffer *buf)
+{
+ char *pos = buf->next;
+ if (pos < buf->buf || pos > buf->buf + buf->buf_size)
+ pos = buf->buf;
+ if (buf->recent && buf->recent[0]) {
+ if (pos <= buf->recent[0])
+ return buf->recent[0] - pos;
+
+ return OSMO_MAX(buf->buf_size - (pos - buf->buf),
+ buf->recent[0] - buf->buf);
+ }
+ return buf->buf_size - (pos - buf->buf);
+}
+
+/*! Re-use static string ring buffer not before five osmo_static_string() calls have occured. */
+static char *default_string_buf_recent[5] = {};
+
+/*! Currently, the largest requested size within libosmocore is 4100 bytes (msgb_hexdump()), allow for enough space so
+ * that it can be called any number of times in a row without hitting the recent[] check. To guarantee N untouched
+ * previous buffers, there has to be space for N+1 buffers. However, a fragmented offset may lead to needing N+2. */
+static char default_string_buf_storage[4100 * (ARRAY_SIZE(default_string_buf_recent) + 2)];
+
+struct osmo_string_ringbuffer osmo_static_string_buf_default = {
+ .buf = default_string_buf_storage,
+ .buf_size = sizeof(default_string_buf_storage),
+ .recent = default_string_buf_recent,
+ .recent_len = ARRAY_SIZE(default_string_buf_recent),
+};
+
+struct osmo_string_ringbuffer *osmo_static_string_buf = &osmo_static_string_buf_default;
+
+/*! Return a static string buffer that can hold the given string length plus an additional nul character, or abort the
+ * program if no buffer is available.
+ *
+ * The idea is to provide distinct string buffers for various osmo_xxx_name() API implementations, so that the same
+ * osmo_xxx_name() function can be used multiple times in the same print format arguments.
+ *
+ * Use osmo_static_string_buf, which can be redirected by the caller to a larger buffer, if required. By default,
+ * osmo_static_string_buf points at osmo_static_string_buf_default, so that no initialization is necessary by the
+ * caller.
+ *
+ * It is the responsibility of the caller to ensure that enough string buffer space is available. If insufficient space
+ * is detected, abort the program using OSMO_ASSERT(false).
+ *
+ * Insufficient space is detected by considering the last N allocations as still used. Depending on the amount of bytes
+ * reserved each time, there can in practice be many more than N allocations without overlapping. If, for example,
+ * osmo_static_string_buf is configured to guarantee 5 allocations of 4100 bytes each without overlaps, that would also
+ * allow for 50 non-overlapping allocations of 410 bytes each. Hence this mechanism merely ensures basic sanity, so that
+ * the caller can at all times be sure that at least 5 concurrent allocations will succeed, and will receive a program
+ * error otherwise.
+ *
+ * \param bufsize The amount of bytes that should be available, caller needs to include terminating nul.
+ * \returns Pointer to string buffer.
+ */
+char *osmo_static_string(size_t bufsize)
+{
+ char *ret = osmo_string_ringbuffer_get(osmo_static_string_buf, bufsize);
+ /* If we're going to assert because of no more static strings being available, print out a status to stderr
+ * first. */
+ if (!ret) {
+ int i;
+ fprintf(stderr, "\n\n"
+ "*** Static ringbuffer full:\n"
+ " avail = %zu\n"
+ " requested %zu\n"
+ " size = %zu\n",
+ osmo_string_ringbuffer_avail(osmo_static_string_buf),
+ bufsize,
+ osmo_static_string_buf->buf_size);
+
+#define PRINT_IDX(val, label_fmt, label_args...) \
+ if (osmo_static_string_buf->val >= osmo_static_string_buf->buf \
+ && osmo_static_string_buf->val <= (osmo_static_string_buf->buf + osmo_static_string_buf->buf_size)) \
+ fprintf(stderr, " [%zu] " label_fmt "\n", \
+ osmo_static_string_buf->val - osmo_static_string_buf->buf, ## label_args); \
+ else \
+ fprintf(stderr, " " label_fmt " out of bounds\n", ## label_args);
+
+ PRINT_IDX(next, "next");
+ if (osmo_static_string_buf->recent) {
+ for (i = 0; i < osmo_static_string_buf->recent_len; i++) {
+ if (!osmo_static_string_buf->recent[i])
+ continue;
+ PRINT_IDX(recent[i], "recent[%d]", i);
+ }
+ }
+
+#undef PRINT_IDX
+ }
+ OSMO_ASSERT(ret);
+ return ret;
+}
+
/*! @} */
diff --git a/tests/utils/utils_test.c b/tests/utils/utils_test.c
index d592fe0..73589d6 100644
--- a/tests/utils/utils_test.c
+++ b/tests/utils/utils_test.c
@@ -1022,6 +1022,115 @@ void strbuf_test()
printf("(need %d chars, had size=63) %s\n", rc, buf);
}
+static void string_ringbuf_test_print_pos(struct osmo_string_ringbuffer *b, char *pos, const char* label)
+{
+ int i;
+ const char *marker = "^";
+ if (pos < b->buf) {
+ pos = b->buf;
+ marker = "<-";
+ }
+ if (pos > b->buf + b->buf_size) {
+ pos = b->buf + b->buf_size + 5;
+ marker = "->";
+ }
+ for (i = 0; i < (pos - b->buf); i++)
+ printf(" ");
+ printf(" " "%s%s\n", marker, label);
+}
+
+void string_ringbuf_test_get(struct osmo_string_ringbuffer *b, size_t len)
+{
+ char *ret = osmo_string_ringbuffer_get(b, len);
+ int i;
+ static char marker = 'a';
+ printf("osmo_string_ringbuffer_get(%2zu) -> ", len);
+ if (!ret)
+ printf("NULL");
+ else {
+
+ printf("buf[%zu]", ret - b->buf);
+ for (i = 0; i < len; i++)
+ ret[i] = marker;
+ }
+ printf("\n");
+
+ printf("buf = [");
+ for (i = 0; i < b->buf_size; i++)
+ printf("%c", b->buf[i]? : '_');
+ printf("]\n");
+ string_ringbuf_test_print_pos(b, b->next, "next");
+ for (i = b->recent_len-1; i >= 0; i--)
+ string_ringbuf_test_print_pos(b, b->recent[i], "recent");
+ printf("avail = %zu\n", osmo_string_ringbuffer_avail(b));
+
+ marker++;
+ if (marker > 'z')
+ marker = 'a';
+}
+
+void string_ringbuf_test()
+{
+ char buf[23] = {};
+ char *recent[3] = {};
+ struct osmo_string_ringbuffer _b = {
+ .buf = buf,
+ .buf_size = sizeof(buf),
+ .recent = recent,
+ .recent_len = ARRAY_SIZE(recent),
+ };
+ struct osmo_string_ringbuffer *b = &_b;
+
+#define CLEAR \
+ memset(buf, 0, sizeof(buf)); \
+ osmo_string_ringbuffer_clear(b);
+
+ int i;
+
+
+ printf("\n\n%s\n", __func__);
+
+ printf("\n*** Test continuous small buffers\n");
+ for (i = 0; i < 26; i++)
+ string_ringbuf_test_get(b, i&1? 5 : 3);
+
+ printf("\n*** Test exact use\n");
+ CLEAR
+ string_ringbuf_test_get(b, 5);
+ string_ringbuf_test_get(b, 5);
+ string_ringbuf_test_get(b, 10);
+ string_ringbuf_test_get(b, 3);
+ string_ringbuf_test_get(b, 5);
+ string_ringbuf_test_get(b, 5);
+ string_ringbuf_test_get(b, 10);
+ string_ringbuf_test_get(b, 3);
+
+ printf("\n*** Test deadlock\n");
+ CLEAR
+ string_ringbuf_test_get(b, 5);
+ string_ringbuf_test_get(b, 15);
+ string_ringbuf_test_get(b, 3);
+ string_ringbuf_test_get(b, 1);
+ string_ringbuf_test_get(b, 1);
+
+ printf("\n*** Test deadlock (2)\n");
+ CLEAR
+ string_ringbuf_test_get(b, 23);
+ string_ringbuf_test_get(b, 1);
+ string_ringbuf_test_get(b, 1);
+
+ printf("\n*** Test bounds checking: available size\n");
+ CLEAR
+ string_ringbuf_test_get(b, 30);
+ string_ringbuf_test_get(b, 10);
+ string_ringbuf_test_get(b, 10);
+ string_ringbuf_test_get(b, 4);
+
+ printf("\nTest bounds checking: invalid args\n");
+ string_ringbuf_test_get(b, 0);
+ OSMO_ASSERT(osmo_string_ringbuffer_get(NULL, 10) == NULL);
+}
+
int main(int argc, char **argv)
{
static const struct log_info log_info = {};
@@ -1040,5 +1149,6 @@ int main(int argc, char **argv)
osmo_sockaddr_to_str_and_uint_test();
osmo_str_tolowupper_test();
strbuf_test();
+ string_ringbuf_test();
return 0;
}
diff --git a/tests/utils/utils_test.ok b/tests/utils/utils_test.ok
index 1215ddd..48574cb 100644
--- a/tests/utils/utils_test.ok
+++ b/tests/utils/utils_test.ok
@@ -342,3 +342,347 @@ cascade:
(need 134 chars)
T minus 10 9 8 7 6 5 4 3 2 1 ... Lift off! -- T minus 10 9 8 7 6 5 4 3 2 1 ... Lift off! -- T minus 10 9 8 7 6 5 4 3 2 1 ... Lift off!
(need 134 chars, had size=63) T minus 10 9 8 7 6 5 4 3 2 1 ... Lift off! -- T minus 10 9 8 7
+
+
+string_ringbuf_test
+
+*** Test continuous small buffers
+osmo_string_ringbuffer_get( 3) -> buf[0]
+buf = [aaa____________________]
+ ^next
+ <-recent
+ <-recent
+ ^recent
+avail = 20
+osmo_string_ringbuffer_get( 5) -> buf[3]
+buf = [aaabbbbb_______________]
+ ^next
+ <-recent
+ ^recent
+ ^recent
+avail = 15
+osmo_string_ringbuffer_get( 3) -> buf[8]
+buf = [aaabbbbbccc____________]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 12
+osmo_string_ringbuffer_get( 5) -> buf[11]
+buf = [aaabbbbbcccddddd_______]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 7
+osmo_string_ringbuffer_get( 3) -> buf[16]
+buf = [aaabbbbbcccdddddeee____]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 8
+osmo_string_ringbuffer_get( 5) -> buf[0]
+buf = [fffffbbbcccdddddeee____]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 6
+osmo_string_ringbuffer_get( 3) -> buf[5]
+buf = [fffffgggcccdddddeee____]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 8
+osmo_string_ringbuffer_get( 5) -> buf[8]
+buf = [fffffggghhhhhdddeee____]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 10
+osmo_string_ringbuffer_get( 3) -> buf[13]
+buf = [fffffggghhhhhiiieee____]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 7
+osmo_string_ringbuffer_get( 5) -> buf[16]
+buf = [fffffggghhhhhiiijjjjj__]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 8
+osmo_string_ringbuffer_get( 3) -> buf[0]
+buf = [kkkffggghhhhhiiijjjjj__]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 10
+osmo_string_ringbuffer_get( 5) -> buf[3]
+buf = [kkklllllhhhhhiiijjjjj__]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 8
+osmo_string_ringbuffer_get( 3) -> buf[8]
+buf = [kkklllllmmmhhiiijjjjj__]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 12
+osmo_string_ringbuffer_get( 5) -> buf[11]
+buf = [kkklllllmmmnnnnnjjjjj__]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 7
+osmo_string_ringbuffer_get( 3) -> buf[16]
+buf = [kkklllllmmmnnnnnooojj__]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 8
+osmo_string_ringbuffer_get( 5) -> buf[0]
+buf = [ppppplllmmmnnnnnooojj__]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 6
+osmo_string_ringbuffer_get( 3) -> buf[5]
+buf = [pppppqqqmmmnnnnnooojj__]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 8
+osmo_string_ringbuffer_get( 5) -> buf[8]
+buf = [pppppqqqrrrrrnnnooojj__]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 10
+osmo_string_ringbuffer_get( 3) -> buf[13]
+buf = [pppppqqqrrrrrsssooojj__]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 7
+osmo_string_ringbuffer_get( 5) -> buf[16]
+buf = [pppppqqqrrrrrsssttttt__]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 8
+osmo_string_ringbuffer_get( 3) -> buf[0]
+buf = [uuuppqqqrrrrrsssttttt__]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 10
+osmo_string_ringbuffer_get( 5) -> buf[3]
+buf = [uuuvvvvvrrrrrsssttttt__]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 8
+osmo_string_ringbuffer_get( 3) -> buf[8]
+buf = [uuuvvvvvwwwrrsssttttt__]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 12
+osmo_string_ringbuffer_get( 5) -> buf[11]
+buf = [uuuvvvvvwwwxxxxxttttt__]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 7
+osmo_string_ringbuffer_get( 3) -> buf[16]
+buf = [uuuvvvvvwwwxxxxxyyytt__]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 8
+osmo_string_ringbuffer_get( 5) -> buf[0]
+buf = [zzzzzvvvwwwxxxxxyyytt__]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 6
+
+*** Test exact use
+osmo_string_ringbuffer_get( 5) -> buf[0]
+buf = [aaaaa__________________]
+ ^next
+ <-recent
+ <-recent
+ ^recent
+avail = 18
+osmo_string_ringbuffer_get( 5) -> buf[5]
+buf = [aaaaabbbbb_____________]
+ ^next
+ <-recent
+ ^recent
+ ^recent
+avail = 13
+osmo_string_ringbuffer_get(10) -> buf[10]
+buf = [aaaaabbbbbcccccccccc___]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 3
+osmo_string_ringbuffer_get( 3) -> buf[20]
+buf = [aaaaabbbbbccccccccccddd]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 5
+osmo_string_ringbuffer_get( 5) -> buf[0]
+buf = [eeeeebbbbbccccccccccddd]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 5
+osmo_string_ringbuffer_get( 5) -> buf[5]
+buf = [eeeeefffffccccccccccddd]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 10
+osmo_string_ringbuffer_get(10) -> buf[10]
+buf = [eeeeefffffggggggggggddd]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 3
+osmo_string_ringbuffer_get( 3) -> buf[20]
+buf = [eeeeefffffgggggggggghhh]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 5
+
+*** Test deadlock
+osmo_string_ringbuffer_get( 5) -> buf[0]
+buf = [iiiii__________________]
+ ^next
+ <-recent
+ <-recent
+ ^recent
+avail = 18
+osmo_string_ringbuffer_get(15) -> buf[5]
+buf = [iiiiijjjjjjjjjjjjjjj___]
+ ^next
+ <-recent
+ ^recent
+ ^recent
+avail = 3
+osmo_string_ringbuffer_get( 3) -> buf[20]
+buf = [iiiiijjjjjjjjjjjjjjjkkk]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 0
+osmo_string_ringbuffer_get( 1) -> NULL
+buf = [iiiiijjjjjjjjjjjjjjjkkk]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 0
+osmo_string_ringbuffer_get( 1) -> NULL
+buf = [iiiiijjjjjjjjjjjjjjjkkk]
+ ^next
+ ^recent
+ ^recent
+ ^recent
+avail = 0
+
+*** Test deadlock (2)
+osmo_string_ringbuffer_get(23) -> buf[0]
+buf = [nnnnnnnnnnnnnnnnnnnnnnn]
+ ^next
+ <-recent
+ <-recent
+ ^recent
+avail = 0
+osmo_string_ringbuffer_get( 1) -> NULL
+buf = [nnnnnnnnnnnnnnnnnnnnnnn]
+ ^next
+ <-recent
+ <-recent
+ ^recent
+avail = 0
+osmo_string_ringbuffer_get( 1) -> NULL
+buf = [nnnnnnnnnnnnnnnnnnnnnnn]
+ ^next
+ <-recent
+ <-recent
+ ^recent
+avail = 0
+
+*** Test bounds checking: available size
+osmo_string_ringbuffer_get(30) -> NULL
+buf = [_______________________]
+ <-next
+ <-recent
+ <-recent
+ <-recent
+avail = 23
+osmo_string_ringbuffer_get(10) -> buf[0]
+buf = [rrrrrrrrrr_____________]
+ ^next
+ <-recent
+ <-recent
+ ^recent
+avail = 13
+osmo_string_ringbuffer_get(10) -> buf[10]
+buf = [rrrrrrrrrrssssssssss___]
+ ^next
+ <-recent
+ ^recent
+ ^recent
+avail = 3
+osmo_string_ringbuffer_get( 4) -> NULL
+buf = [rrrrrrrrrrssssssssss___]
+ ^next
+ <-recent
+ ^recent
+ ^recent
+avail = 3
+
+Test bounds checking: invalid args
+osmo_string_ringbuffer_get( 0) -> NULL
+buf = [rrrrrrrrrrssssssssss___]
+ ^next
+ <-recent
+ ^recent
+ ^recent
+avail = 3