Neels Hofmeyr has uploaded this change for review. ( https://gerrit.osmocom.org/13061
Change subject: add osmo_string_ringbuffer and osmo_static_string() API ...................................................................... add osmo_string_ringbuffer and osmo_static_string() API Change-Id: I48f8951de4d209d4cd3ca1aa9ce6137918913125 --- M include/osmocom/core/utils.h M src/utils.c M tests/utils/utils_test.c M tests/utils/utils_test.ok 4 files changed, 639 insertions(+), 0 deletions(-) git pull ssh://gerrit.osmocom.org:29418/libosmocore refs/changes/61/13061/1 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 @@ #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 @@ 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 @@ 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 @@ 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 @@ (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 -- To view, visit https://gerrit.osmocom.org/13061 To unsubscribe, or for help writing mail filters, visit https://gerrit.osmocom.org/settings Gerrit-Project: libosmocore Gerrit-Branch: master Gerrit-MessageType: newchange Gerrit-Change-Id: I48f8951de4d209d4cd3ca1aa9ce6137918913125 Gerrit-Change-Number: 13061 Gerrit-PatchSet: 1 Gerrit-Owner: Neels Hofmeyr <nhofm...@sysmocom.de>