12 ms·

Simple Dynamic Strings library for C

214 points by antirez 13y ago

antirez 13y ago
I forked sds.c from Redis given that it was very useful for the project for years, so I guess it may be useful in other contexts as well. There are a few changes at API level compared to the Redis sds.c file, however most of the work went into documenting it.
unwind 13y ago
Nice, thanks for contributing (even more). I haven't read much of the code at all, but a minor suggestion would be to change: struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr))); to struct sdshdr *sh = (void*)(s-sizeof *sh); since the entire idea is that the pointer on the left-hand side is to the type whose size should be subtracted, I think it's better not to repeat the type but to "lock it" to the pointer instead. This also (of course) means we can drop the parenthesis with sizeof, since those are only needed when its argument is a type name.
- antirez 13y ago
  Thanks unwind, this is much better indeed! Fixing. EDIT: Fixed here: https://github.com/antirez/sds/commit/c636fc6cd25e455a75dca24ac08ba736f62db6c8 https://github.com/antirez/sds/commit/c636fc6cd25e455a75dca2... Seems everything is still working but I need definitely more unit tests... Note everything is covered right now.
  - gandalf013 13y ago
    A more correct version might be: #include <stddef.h> int buf_offset = (int)offsetof(struct sdshdr, buf); struct sdshdr *sh = s - buf_offset; This is because the compiler might insert padding between your struct elements and the flexible array member. In your case, you're using only int types in the header, so padding shouldn't be an issue on most architectures, but consider the following: struct header { int i; char c; char data[]; }; sizeof(struct header) on my machine is 8, but "data" starts at an offset of 5 from the beginning of the struct. So, to go from "data" pointer to the pointer representing the beginning of the struct, you will need to subtract 5, not 8. Here is a test program: #include <stdio.h> #include <stddef.h> struct header { int i; char c; char data[]; }; int main(void) { struct header h = {0}; printf("offsetof %zu\n", offsetof(struct header, data)); printf("sizeof %zu\n", sizeof h); printf("start %p, data start %p, delta %d\n", (void *)&h, (void *)(h.data), (int)((char *)h.data - (char *)&h)); return 0; } http://std.dkuug.dk/JTC1/SC22/WG14/www/docs/n983.htm http://std.dkuug.dk/JTC1/SC22/WG14/www/docs/n983.htm is relevant for this case as well.
    - deletes 13y ago
      Thank you for that. That surprised me. I thought( and read somewhere ) that the flexible array member comes right after the entire struct, which includes possible padding. OP got away with it since he always allocates the size of the entire struct, which is 8, plus the string size. And since char doesn't have any alignment requirements it doesn't matter, because he always gets back to correct offset. So data member is basically not used, and if you check the code you will see that it actually in never used!
      - gandalf013 13y ago
        The standard actually specifies (or specified?) that the flexible array member must come after all the members, including the padding. But, from my reading, that wasn't their intent, and is certainly not how compilers implement it. The link in my original post is an acknowledgement from the committee about this and that the standard needs to be updated. I think the main reason the OP got away with it is because in his structure, "sizeof(struct sdshdr)" is equal to the offset of "buf" in the struct. This is not necessarily true. In particular, see the latest C standard draft (http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf), section 6.7.2.1 (Structure and union specifiers), paragraph 18 and 20-21. An example in the standard uses this code: struct s { int n; double d[]; }; and says that "but it is possible that" sizeof (struct s) >= offsetof(struct s, d) + sizeof (double)
        deletes 13y ago
        Yeah I was wrong on that, he must have sizes 8 both. My compiler gives 5 and 8. Coincidentally I just read that specific paragraph earlier today for totally different reasons. :) Will have to recheck some code.
    - unwind 13y ago
      Very true of course, I guess I assumed that antirez had thought of that, should have noticed that there were no packing enhchantmens on the struct. I love offsetof() for code like this.
- simias 13y ago
  Heh, you're the first person I meet who advocates dropping the parens around the sizeof argument in any situation. That does look terribly alien to me.
  - breadbox 13y ago
    Really? I always do. If you don't, it makes the variable look like a type. It's the same reason why I dislike extra parens around the value in the return statement. Don't make it look like something it isn't.
  - adestefan 13y ago
    sizeof is a unary operator and not a function. Only types need to be enclosed in parens. Most people don't know this.
    - unwind 13y ago
      Exactly! For some reason this anti-pattern is very thoroughly entrenched among C programmers and it's so very frustrating. My other favorite is casting the return value of malloc(), something you see a great deal of and that I always oppose. See http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc http://stackoverflow.com/questions/605845/do-i-cast-the-resu... for my best arguments.
      - Narishma 13y ago
        Casting the return value of malloc is necessary in C++. I think that's why it's so widespread, so you can compile your C program with a C++ compiler.
gtrubetskoy 13y ago
I've had the pleasure of getting pretty deep into sds back when I was tinkering with thredis, and it's definitely very cool.
FooBarWidget 13y ago
Sigh, another string library. And this is the reason why I prefer C++ over C. You don't end up writing another string library for the 300th time. There aren't that many differences between string libraries anyway. Most of them are just structs with a pointer to a memory block, plus a length field.
- antirez 13y ago
  Yep, but this one has not the usual layout of struct+pointer (that's the whole point), and I'm not sure it qualifies as "yet another" since it was written in 2006.
  - FooBarWidget 13y ago
    You're right, sorry. I only scanned the document, saw the struct, and closed the tab. The way you use a header before the data is similar to how Ruby represents its strings internally.
  - pacaro 13y ago
    It appears to me to be "yet another" because the length before the string approach is usually referred to as a b-string. windows (for example) has had a comprehensive b-string library (type is called BSTR) for about 20 years - due to it's age and provenance it has the downside of thinking a character is a 16-bit value...
    - shadowfox 13y ago
      Just to add a reference to the parent: http://www.johndcook.com/cplusplus_strings.html http://www.johndcook.com/cplusplus_strings.html (The article is mildly interesting by itself)
- pekk 13y ago
  Yes, many people who have written much C have written some version of this library.
- jhallenworld 13y ago
sparkie 13y ago
Disadvantage #1 isn't really a disadvantage in modern computing, it's the right thing to do.
- aidenn0 13y ago
  I strongly disagree. It is a tradeoff between that and advantages #1 and #3; with the bstring library, for example, you pass in a mutable string and the function mutates it. In no world is passing in a mutable value, having it mutate it, but then having to reassigning your variable superior. Passing in an immutable value, and then assigning a fresh value is reasonable, but that's not what SDS is doing, AFAICT. I think gcc has some decorations you can have to tell it to never ignore the return function. I'm curious why s = sdscat(s,"Some more data"); didin't end up like: sdscat(&s,"Some more data");
deleted 13y ago
[deleted]
- matthiasv 13y ago
  > SDS is a string library for C [...] Function overloading does not exist in C.
- deleted 13y ago
  [deleted]
- rossy 13y ago
  C99 doesn't support function overloading. I guess that style is used by everything that wants to expose a C compatible API. Come to think of it, it might be possible to do that with C11 _Generic.
  - antirez 13y ago
    And... SDS and plain strings are both char pointers so even with _Generic it is probably not possible to do that.
wbond 13y ago
Recently I've been getting into some C and having programmed in a number of other languages know enough to be sure I wanted to have a solid understanding of properly handling encodings and strings in general. I've obtained a good understanding, but now I am looking to abstract some of the low-level mechanics. Unfortunately most of the libraries I have seen (such as bstring) use structs. It was nice to see this approach taken. Thanks for extracting it and making it easy to find and learn about! On a related note - does anyone have recommendations for a similar small library for dealing with conversions from char * to wchar_t * and basic encoding duties? I'm working cross-platform, and so far I've stitched together some functions wrapping stuff like wcsrtombs() and WideCharToMultiByte().
Aardwolf 13y ago
The biggest missing thing in C imho is destructors, because you need to manually clean up everything whenever you leave a scope or function. That means calling "free" at every exit point. Or alternatively, putting one "cleanup:" label at the end of the function and using "goto cleanup;" instead of break or return everywhere. But goto is considered harmful, so that handy pattern seems unclean. My question is: do you consider the "goto cleanup" pattern clean or not, and if not, what are better alternatives?
- antirez 13y ago
  Goto for cleanup is not bad IMHO. I use it extensively... $ cd redis; grep goto *.c | wc -l 251 All the instances are like: goto cleanup; goto error; goto badfmt; goto numargserr; In this context is easy to read and makes the code structure better.
  - coherentpony 13y ago
    I don't see the difference between this and cleanup(state); error(state); etc. Just pull them each out into a function. You're still DRY and don't lose flow control. In my honest opinion, there is never a need for goto.
    - dllthomas 13y ago
      If you are constructing arguments in order, you can destroy them in the reverse order at the exit and this lets you cleanly handle a failure in the middle of allocations: thing1 = allocate_thing1(); if(!thing1) goto cleanup1; thing2 = allocate_thing2(); if(!thing2) goto cleanup2; ... cleanup3: deallocate_thing2(thing2); cleanup2: deallocate_thing1(thing1); cleanup1: return;
    - scott_s 13y ago
      Because sometimes the tasks you need to perform cascade, and then you're repeating that cascade all over the place. As I pointed out upthread, check out the Linux kernel: http://lxr.free-electrons.com/source/kernel/fork.c?v=3.3#L427 http://lxr.free-electrons.com/source/kernel/fork.c?v=3.3#L42... Notice the cascade after the 'out' label; each label after it is for a different level of cleanup needed, depending on how deep into the system call the function encountered the error. Also notice that this is basically the kind of code one would generate for exceptions.
shadowfox 13y ago
At some point in time, I found this list of C String libraries with some comparisons: http://www.and.org/vstr/comparison http://www.and.org/vstr/comparison The (different) approaches taken by many of these libraries are interesting.
- emmelaich 13y ago
  A great list. I'd add the str bits of http://libslack.org/ http://libslack.org/ to that list.
Marat_Dukhan 13y ago
This is neat, but please add a pointer to deallocation function to sds header and use it in sdsfree. This will allow to return sds strings from functions in shared libraries. A common problem it that the user of the library might use a different version of libc than the shared library (this is especially typical on Windows), and when it calls sdsfree on an sds string allocated with a different libc, something awful will happen (in the best case, it will just leak memory). By storing a pointer to the deallocation function in the code which allocated the string you can make sure that it is always released by the same libc version that allocated it.
angersock 13y ago
So, this is an interesting approach to strings: It's basically a malloc()/free() implementation with printf, some formatting, and strcat bolted onto it. (Strictly speaking, it may or may not use free lists or whatever, but the use of the header and returned pointer is quite similar.) And that's awesome.
dmunoz 13y ago
I think the library is great, and don't have a whole lot to say about it, but wanted to mention one tangentially related thing: The README on this repo is awesome. Opening up with advantages and disadvantages? Awesome. Plenty of code examples covering all of the major use cases? Awesome. Quick overview of the internals? AWESOME! Quick two line note about how to use the library in your project? Awesome. I'm tempted to rant about how I wish documentation was taken more seriously, and that programmers seem to make it a point of pride that spending the first half hour with a library figuring out how to actually use it is just something we have to deal with as programmers, but I won't do so aside from this single sentence.
- wting 13y ago
  man pages used to be treated with the same reverence, but nowadays nobody seems to bother. I have pretty extensive man pages for some of my open source stuff, but it doesn't seem to help with users downstream.
  - deeviant 13y ago
    To be honest, I pretty much hate man pages. They almost never have examples(Is that some sort of rule?), they have no "quick summary of the shit you use 95% of the time", and they get generally written as a novel, seemingly from the perspective of the developer of the util rather than consumer. Mind you, I have used man pages many times before, but only because it was the best source of information, not because it was a particularly efficent one. The Markdown README of this string library is a thousand times better than any man page I have seen.
    - ploxiln 13y ago
      man pages start with the function prototypes, that's your "quick summary". Near the end there can be an examples section, and many man pages have one. If I run "man 3 open" I see a reasonable examples section. I like manpages because I'm already editing or running programs in the terminal, and I can pop open the man page in the terminal quite quickly and conveniently, without a search online or even a single network request, without reaching for the mouse, etc.
numeromancer 13y ago
NB: In the following function: /* Like sdscatpritf() but gets va_list instead of being variadic. */ sds sdscatvprintf(sds s, const char *fmt, va_list ap) { va_list cpy; char *buf, *t; size_t buflen = 16; while(1) { buf = malloc(buflen); if (buf == NULL) return NULL; buf[buflen-2] = '\0'; va_copy(cpy,ap); vsnprintf(buf, buflen, fmt, cpy); va_end(cpy); // <--- add this ---- if (buf[buflen-2] != '\0') { free(buf); buflen *= 2; continue; } break; } t = sdscat(s, buf); free(buf); return t; } From the `man va_copy` on my system: Each invocation of va_copy() must be matched by a corresponding invocation of va_end() in the same function. This is not likely to be a problem in most systems, but it can't hurt to be formally correct.
- fmela 13y ago
  I think you meant "va_end(ap);". Created a pull request for you: https://github.com/antirez/sds/pull/8 https://github.com/antirez/sds/pull/8
  - numeromancer 13y ago
    No, I'm pretty sure that `va_end(cpy)` is correct. `ap` is the `va_list` passed into the function. `cpy` is the local copy.
    - fmela 13y ago
      You're right. Fixed.
scottlamb 13y ago
Disadvantage #1 seems unnecessary. Instead of this: s = sdscat(s,"Some more data"); Why not do this? sdscat(&s,"Some more data"); The latter would make the use-after-free error they're describing impossible. (Disadvantage #2, changing one reference but not others, would remain. And callers would still need to check for NULL if they intend to handle ENOMEM gracefully.) I assert there's no meaningful performance difference between the two.
- paraboul 13y ago
  To be consistent between allocation and reallocation (like malloc() and realloc()). And you still want to access the old value if reallocation failed.
  - clarry 13y ago
    To be fair, the library already assigns returns from realloc in such a way that you cannot retrieve the old data if realloc failed. Not nice I know.
  - scottlamb 13y ago
    > To be consistent between allocation and reallocation (like malloc() and realloc()). Consistency is a tool that is often useful to promote program correctness. You're suggesting using it to accomplish the reverse. If it's important aesthetically that all sds operations be consistent in this regard, you can structure the allocation interface in the same way: sdserror sdsnew(sds*); sds mystring = NULL; sdsnew(&mystring, "Hello World!"); This is a common practice in relatively new interfaces like pthread_create. > And you still want to access the old value if reallocation failed. If you want to provide commit-or-rollback semantics, you could signal error via return value rather than by replacing s with NULL: if (sdscat(&s,"Some more data") != SDS_SUCCESS) { /* failure path; s is unchanged */ } else { /* s now has "Some more data in it" */ } but this may be completely useless, depending on the environment(s) in which the library or program is intended to be used. On 64-bit Linux systems with memory overcommit enabled (the default), this failure path essentially shouldn't ever happen. Instead, some process (maybe yours, maybe not) will be picked by the kernel OOM killer. Many programs just use an allocate-or-die interface, as the sds README mentions.
_paulc 13y ago
Excellent news - the Redis source code is a really good source of high quality dependency-free C code and tends to be the first place I look. Some time ago I forked the SDS code and added a set of additional utility functions around this for a project I was working on at the time (basic file reading, regex, LZF compression, Blowfish encrypt/decrypt, SHA256 etc). This was from a fairly old SDS version so this looks like a good opportunity to sync up with the library version. Repository is here: https://github.com/paulchakravarti/sdsutils https://github.com/paulchakravarti/sdsutils
eis 13y ago
Disadvantage #1 can be simply solved by using a pointer to the "sds" type instead. Then you can be sure that sdscat(&s, "Some more data") updates s to always point at the right memory address and you can't introduce hard to find bugs by forgetting to assign to s which the compiler wont warn you about. If you'd pass just "s" instead of "&s" as the first parameter, the compiler would error out. So all functions modifying the string should take a pointer to it.
- paraboul 13y ago
  To be consistent between allocation and reallocation (like malloc() and realloc()). And you still want to access the old value if reallocation failed.
clarry 13y ago
Mixing signed and unsigned arithmetic operands. Not doing trivial overflow checking before arithmetic. Using results from said arithmetic as indices or starting points for memory writes. My gut says that any application using this library to process untrusted input is exploitable. Of course, it was never advertised as being secure :-) Which is unusual, as many "better strings" libraries make claims about the security of the traditional way of string handling (and then go on to do it wrong). Edit: To give a concrete example, someone here recommended BString just a few days ago. That library has a "security statement" in which it claims to prevent overflow type attacks by using signed integers instead of size_t, and then checking whether the result is negative after arithmetic. But signed overflow is undefined behavior in C, and these are not guaranteed to wrap around. And yes such things have been exploited. I don't know how likely or easy bstring is to "own" but in any case it's doinnit wrong. And yes I checked the code, it does what it claims to do..
- adobriyan 13y ago
  > prevent overflow type attacks by using signed integers instead of size_t, and then checking whether the result is negative after arithmetic Whoa! As if checking for overflow with unsigned is impossible...
- antirez 13y ago
  Hello clarry, I don't think there are APIs that if not grossly misused will lead to security issues in general. There is one issue I'm aware of that perhaps is not easily exploitable but surely is unexpected behavior, that is, overflow when you reach a 2GB string: that requires a check in sdsMakeRoomFor() for sure. Note that this could be fixed by using uint64_t type for example in the header, however in the original incarnation of SDS inside Redis this was not possible for memory usage concerns. In the standalone library I believe it is instead a great idea, since 2GB is no longer an acceptable limit. From the point of view of the security the most concerning function looks like sdsrange(), there are sanity checks in place to avoid that indexes received from the outside can lead to issues, but I'll do a security review in the future in order to formally check for issues.
  - 13y ago
vvde 13y ago
Making sds a typedef for char* is very convenient. But it makes it very easy to pass an sds to a function that expects a C string without checking for null bytes. Ruby, Java, Perl, PHP have all had security problems when interacting with C because they failed to properly distinguish binary-safe strings and C strings. http://insecure.org/news/P55-07.txt http://insecure.org/news/P55-07.txt http://cwe.mitre.org/data/definitions/626.html http://cwe.mitre.org/data/definitions/626.html
- kzrdude 13y ago
  I'd prefer a typesafe version (that would be a library with a struct type). It could even be a trivial wrapper struct for the char *.
oh_sigh 13y ago
In the case of disadvantage #1: s = sdscat(s,"Some more data"); You could fix that by adding a "remote pointer" header field. Inside of sdscat, you would allocate a new sds struct, and set the remote pointer header field in `s` to the new sds structs location. You could also try to do a realloc and maybe youll get the same starting pointer back again.
sdegutis 13y ago
My biggest gripe with C's string functions is that it's really easy to make off-by-one errors when trying to do anything with two strings, due to NUL and the way they seem to handle it inconsistently. I'm constantly having to check the docs for any given string function to find out how it handles NUL (which isn't always in an obvious spot thanks to the design of man pages). And once I've found it, I have to come up with some contrived example that usually needs to be written in a comment just to make sure I've used its intended algorithm correctly and didn't cause an off-by-one error. If this library hides all that for me, I'm sold.
mbreese 13y ago
How much better is this dynamic approach than something like immutable strings? (not that char* is immutable) Since with the sds library, you could potentially be getting back a new pointer for each operation, you could just as easily be working from an immutable string library. Do immutable strings have poor performance? I've never really considered it.
wildmXranat 13y ago
I remember lifting the 'sds' string implementation from within the redis back in the day. Thanks antirez
codys 13y ago
ustr [1] is another library to consider. It uses a variable sized header to avoid having large (percentage wise) overhead for short strings. 1: http://www.and.org/ustr/ http://www.and.org/ustr/
acqq 13y ago
The CString C++ class from Microsoft's MFC and now also ATL used since forever the trick of having both the length and the reference counting in the single allocation with the characters themselves, as well as additional 0-termination character even if it was initialized with non-zero terminated character.
wereHamster 13y ago
How does it compare to strbuf that is used in git?

214 points by antirez 13y ago

I forked sds.c from Redis given that it was very useful for the project for years, so I guess it may be useful in other contexts as well. There are a few changes at API level compared to the Redis sds.c file, however most of the work went into documenting it.

unwind 13y ago

Nice, thanks for contributing (even more). I haven't read much of the code at all, but a minor suggestion would be to change: struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr))); to struct sdshdr *sh = (void*)(s-sizeof *sh); since the entire idea is that the pointer on the left-hand side is to the type whose size should be subtracted, I think it's better not to repeat the type but to "lock it" to the pointer instead. This also (of course) means we can drop the parenthesis with sizeof, since those are only needed when its argument is a type name.

antirez 13y ago
Thanks unwind, this is much better indeed! Fixing. EDIT: Fixed here: https://github.com/antirez/sds/commit/c636fc6cd25e455a75dca24ac08ba736f62db6c8 https://github.com/antirez/sds/commit/c636fc6cd25e455a75dca2... Seems everything is still working but I need definitely more unit tests... Note everything is covered right now.
- gandalf013 13y ago
  A more correct version might be: #include <stddef.h> int buf_offset = (int)offsetof(struct sdshdr, buf); struct sdshdr *sh = s - buf_offset; This is because the compiler might insert padding between your struct elements and the flexible array member. In your case, you're using only int types in the header, so padding shouldn't be an issue on most architectures, but consider the following: struct header { int i; char c; char data[]; }; sizeof(struct header) on my machine is 8, but "data" starts at an offset of 5 from the beginning of the struct. So, to go from "data" pointer to the pointer representing the beginning of the struct, you will need to subtract 5, not 8. Here is a test program: #include <stdio.h> #include <stddef.h> struct header { int i; char c; char data[]; }; int main(void) { struct header h = {0}; printf("offsetof %zu\n", offsetof(struct header, data)); printf("sizeof %zu\n", sizeof h); printf("start %p, data start %p, delta %d\n", (void *)&h, (void *)(h.data), (int)((char *)h.data - (char *)&h)); return 0; } http://std.dkuug.dk/JTC1/SC22/WG14/www/docs/n983.htm http://std.dkuug.dk/JTC1/SC22/WG14/www/docs/n983.htm is relevant for this case as well.
  - deletes 13y ago
    Thank you for that. That surprised me. I thought( and read somewhere ) that the flexible array member comes right after the entire struct, which includes possible padding. OP got away with it since he always allocates the size of the entire struct, which is 8, plus the string size. And since char doesn't have any alignment requirements it doesn't matter, because he always gets back to correct offset. So data member is basically not used, and if you check the code you will see that it actually in never used!
    - gandalf013 13y ago
      The standard actually specifies (or specified?) that the flexible array member must come after all the members, including the padding. But, from my reading, that wasn't their intent, and is certainly not how compilers implement it. The link in my original post is an acknowledgement from the committee about this and that the standard needs to be updated. I think the main reason the OP got away with it is because in his structure, "sizeof(struct sdshdr)" is equal to the offset of "buf" in the struct. This is not necessarily true. In particular, see the latest C standard draft (http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf), section 6.7.2.1 (Structure and union specifiers), paragraph 18 and 20-21. An example in the standard uses this code: struct s { int n; double d[]; }; and says that "but it is possible that" sizeof (struct s) >= offsetof(struct s, d) + sizeof (double)
      - deletes 13y ago
        Yeah I was wrong on that, he must have sizes 8 both. My compiler gives 5 and 8. Coincidentally I just read that specific paragraph earlier today for totally different reasons. :) Will have to recheck some code.
  - unwind 13y ago
    Very true of course, I guess I assumed that antirez had thought of that, should have noticed that there were no packing enhchantmens on the struct. I love offsetof() for code like this.
simias 13y ago
Heh, you're the first person I meet who advocates dropping the parens around the sizeof argument in any situation. That does look terribly alien to me.
- breadbox 13y ago
  Really? I always do. If you don't, it makes the variable look like a type. It's the same reason why I dislike extra parens around the value in the return statement. Don't make it look like something it isn't.
- adestefan 13y ago
  sizeof is a unary operator and not a function. Only types need to be enclosed in parens. Most people don't know this.
  - unwind 13y ago
    Exactly! For some reason this anti-pattern is very thoroughly entrenched among C programmers and it's so very frustrating. My other favorite is casting the return value of malloc(), something you see a great deal of and that I always oppose. See http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc http://stackoverflow.com/questions/605845/do-i-cast-the-resu... for my best arguments.
    - Narishma 13y ago
      Casting the return value of malloc is necessary in C++. I think that's why it's so widespread, so you can compile your C program with a C++ compiler.

gtrubetskoy 13y ago

I've had the pleasure of getting pretty deep into sds back when I was tinkering with thredis, and it's definitely very cool.

FooBarWidget 13y ago

Sigh, another string library. And this is the reason why I prefer C++ over C. You don't end up writing another string library for the 300th time. There aren't that many differences between string libraries anyway. Most of them are just structs with a pointer to a memory block, plus a length field.

antirez 13y ago
Yep, but this one has not the usual layout of struct+pointer (that's the whole point), and I'm not sure it qualifies as "yet another" since it was written in 2006.
- FooBarWidget 13y ago
  You're right, sorry. I only scanned the document, saw the struct, and closed the tab. The way you use a header before the data is similar to how Ruby represents its strings internally.
- pacaro 13y ago
  It appears to me to be "yet another" because the length before the string approach is usually referred to as a b-string. windows (for example) has had a comprehensive b-string library (type is called BSTR) for about 20 years - due to it's age and provenance it has the downside of thinking a character is a 16-bit value...
  - shadowfox 13y ago
    Just to add a reference to the parent: http://www.johndcook.com/cplusplus_strings.html http://www.johndcook.com/cplusplus_strings.html (The article is mildly interesting by itself)
pekk 13y ago
Yes, many people who have written much C have written some version of this library.
jhallenworld 13y ago

sparkie 13y ago

Disadvantage #1 isn't really a disadvantage in modern computing, it's the right thing to do.

aidenn0 13y ago
I strongly disagree. It is a tradeoff between that and advantages #1 and #3; with the bstring library, for example, you pass in a mutable string and the function mutates it. In no world is passing in a mutable value, having it mutate it, but then having to reassigning your variable superior. Passing in an immutable value, and then assigning a fresh value is reasonable, but that's not what SDS is doing, AFAICT. I think gcc has some decorations you can have to tell it to never ignore the return function. I'm curious why s = sdscat(s,"Some more data"); didin't end up like: sdscat(&s,"Some more data");

deleted 13y ago

[deleted]

matthiasv 13y ago
> SDS is a string library for C [...] Function overloading does not exist in C.
deleted 13y ago
[deleted]
rossy 13y ago
C99 doesn't support function overloading. I guess that style is used by everything that wants to expose a C compatible API. Come to think of it, it might be possible to do that with C11 _Generic.
- antirez 13y ago
  And... SDS and plain strings are both char pointers so even with _Generic it is probably not possible to do that.

wbond 13y ago

Recently I've been getting into some C and having programmed in a number of other languages know enough to be sure I wanted to have a solid understanding of properly handling encodings and strings in general. I've obtained a good understanding, but now I am looking to abstract some of the low-level mechanics. Unfortunately most of the libraries I have seen (such as bstring) use structs. It was nice to see this approach taken. Thanks for extracting it and making it easy to find and learn about! On a related note - does anyone have recommendations for a similar small library for dealing with conversions from char * to wchar_t * and basic encoding duties? I'm working cross-platform, and so far I've stitched together some functions wrapping stuff like wcsrtombs() and WideCharToMultiByte().

Aardwolf 13y ago

The biggest missing thing in C imho is destructors, because you need to manually clean up everything whenever you leave a scope or function. That means calling "free" at every exit point. Or alternatively, putting one "cleanup:" label at the end of the function and using "goto cleanup;" instead of break or return everywhere. But goto is considered harmful, so that handy pattern seems unclean. My question is: do you consider the "goto cleanup" pattern clean or not, and if not, what are better alternatives?

antirez 13y ago
Goto for cleanup is not bad IMHO. I use it extensively... $ cd redis; grep goto *.c | wc -l 251 All the instances are like: goto cleanup; goto error; goto badfmt; goto numargserr; In this context is easy to read and makes the code structure better.
- coherentpony 13y ago
  I don't see the difference between this and cleanup(state); error(state); etc. Just pull them each out into a function. You're still DRY and don't lose flow control. In my honest opinion, there is never a need for goto.
  - dllthomas 13y ago
    If you are constructing arguments in order, you can destroy them in the reverse order at the exit and this lets you cleanly handle a failure in the middle of allocations: thing1 = allocate_thing1(); if(!thing1) goto cleanup1; thing2 = allocate_thing2(); if(!thing2) goto cleanup2; ... cleanup3: deallocate_thing2(thing2); cleanup2: deallocate_thing1(thing1); cleanup1: return;
  - scott_s 13y ago
    Because sometimes the tasks you need to perform cascade, and then you're repeating that cascade all over the place. As I pointed out upthread, check out the Linux kernel: http://lxr.free-electrons.com/source/kernel/fork.c?v=3.3#L427 http://lxr.free-electrons.com/source/kernel/fork.c?v=3.3#L42... Notice the cascade after the 'out' label; each label after it is for a different level of cleanup needed, depending on how deep into the system call the function encountered the error. Also notice that this is basically the kind of code one would generate for exceptions.

shadowfox 13y ago

At some point in time, I found this list of C String libraries with some comparisons: http://www.and.org/vstr/comparison http://www.and.org/vstr/comparison The (different) approaches taken by many of these libraries are interesting.

emmelaich 13y ago
A great list. I'd add the str bits of http://libslack.org/ http://libslack.org/ to that list.

Marat_Dukhan 13y ago

This is neat, but please add a pointer to deallocation function to sds header and use it in sdsfree. This will allow to return sds strings from functions in shared libraries. A common problem it that the user of the library might use a different version of libc than the shared library (this is especially typical on Windows), and when it calls sdsfree on an sds string allocated with a different libc, something awful will happen (in the best case, it will just leak memory). By storing a pointer to the deallocation function in the code which allocated the string you can make sure that it is always released by the same libc version that allocated it.

angersock 13y ago

So, this is an interesting approach to strings: It's basically a malloc()/free() implementation with printf, some formatting, and strcat bolted onto it. (Strictly speaking, it may or may not use free lists or whatever, but the use of the header and returned pointer is quite similar.) And that's awesome.

dmunoz 13y ago

I think the library is great, and don't have a whole lot to say about it, but wanted to mention one tangentially related thing: The README on this repo is awesome. Opening up with advantages and disadvantages? Awesome. Plenty of code examples covering all of the major use cases? Awesome. Quick overview of the internals? AWESOME! Quick two line note about how to use the library in your project? Awesome. I'm tempted to rant about how I wish documentation was taken more seriously, and that programmers seem to make it a point of pride that spending the first half hour with a library figuring out how to actually use it is just something we have to deal with as programmers, but I won't do so aside from this single sentence.

wting 13y ago
man pages used to be treated with the same reverence, but nowadays nobody seems to bother. I have pretty extensive man pages for some of my open source stuff, but it doesn't seem to help with users downstream.
- deeviant 13y ago
  To be honest, I pretty much hate man pages. They almost never have examples(Is that some sort of rule?), they have no "quick summary of the shit you use 95% of the time", and they get generally written as a novel, seemingly from the perspective of the developer of the util rather than consumer. Mind you, I have used man pages many times before, but only because it was the best source of information, not because it was a particularly efficent one. The Markdown README of this string library is a thousand times better than any man page I have seen.
  - ploxiln 13y ago
    man pages start with the function prototypes, that's your "quick summary". Near the end there can be an examples section, and many man pages have one. If I run "man 3 open" I see a reasonable examples section. I like manpages because I'm already editing or running programs in the terminal, and I can pop open the man page in the terminal quite quickly and conveniently, without a search online or even a single network request, without reaching for the mouse, etc.

numeromancer 13y ago

NB: In the following function: /* Like sdscatpritf() but gets va_list instead of being variadic. */ sds sdscatvprintf(sds s, const char *fmt, va_list ap) { va_list cpy; char *buf, *t; size_t buflen = 16; while(1) { buf = malloc(buflen); if (buf == NULL) return NULL; buf[buflen-2] = '\0'; va_copy(cpy,ap); vsnprintf(buf, buflen, fmt, cpy); va_end(cpy); // <--- add this ---- if (buf[buflen-2] != '\0') { free(buf); buflen *= 2; continue; } break; } t = sdscat(s, buf); free(buf); return t; } From the `man va_copy` on my system: Each invocation of va_copy() must be matched by a corresponding invocation of va_end() in the same function. This is not likely to be a problem in most systems, but it can't hurt to be formally correct.

fmela 13y ago
I think you meant "va_end(ap);". Created a pull request for you: https://github.com/antirez/sds/pull/8 https://github.com/antirez/sds/pull/8
- numeromancer 13y ago
  No, I'm pretty sure that `va_end(cpy)` is correct. `ap` is the `va_list` passed into the function. `cpy` is the local copy.
  - fmela 13y ago
    You're right. Fixed.

scottlamb 13y ago

Disadvantage #1 seems unnecessary. Instead of this: s = sdscat(s,"Some more data"); Why not do this? sdscat(&s,"Some more data"); The latter would make the use-after-free error they're describing impossible. (Disadvantage #2, changing one reference but not others, would remain. And callers would still need to check for NULL if they intend to handle ENOMEM gracefully.) I assert there's no meaningful performance difference between the two.

paraboul 13y ago
To be consistent between allocation and reallocation (like malloc() and realloc()). And you still want to access the old value if reallocation failed.
- clarry 13y ago
  To be fair, the library already assigns returns from realloc in such a way that you cannot retrieve the old data if realloc failed. Not nice I know.
- scottlamb 13y ago
  > To be consistent between allocation and reallocation (like malloc() and realloc()). Consistency is a tool that is often useful to promote program correctness. You're suggesting using it to accomplish the reverse. If it's important aesthetically that all sds operations be consistent in this regard, you can structure the allocation interface in the same way: sdserror sdsnew(sds*); sds mystring = NULL; sdsnew(&mystring, "Hello World!"); This is a common practice in relatively new interfaces like pthread_create. > And you still want to access the old value if reallocation failed. If you want to provide commit-or-rollback semantics, you could signal error via return value rather than by replacing s with NULL: if (sdscat(&s,"Some more data") != SDS_SUCCESS) { /* failure path; s is unchanged */ } else { /* s now has "Some more data in it" */ } but this may be completely useless, depending on the environment(s) in which the library or program is intended to be used. On 64-bit Linux systems with memory overcommit enabled (the default), this failure path essentially shouldn't ever happen. Instead, some process (maybe yours, maybe not) will be picked by the kernel OOM killer. Many programs just use an allocate-or-die interface, as the sds README mentions.

_paulc 13y ago

Excellent news - the Redis source code is a really good source of high quality dependency-free C code and tends to be the first place I look. Some time ago I forked the SDS code and added a set of additional utility functions around this for a project I was working on at the time (basic file reading, regex, LZF compression, Blowfish encrypt/decrypt, SHA256 etc). This was from a fairly old SDS version so this looks like a good opportunity to sync up with the library version. Repository is here: https://github.com/paulchakravarti/sdsutils https://github.com/paulchakravarti/sdsutils

eis 13y ago

Disadvantage #1 can be simply solved by using a pointer to the "sds" type instead. Then you can be sure that sdscat(&s, "Some more data") updates s to always point at the right memory address and you can't introduce hard to find bugs by forgetting to assign to s which the compiler wont warn you about. If you'd pass just "s" instead of "&s" as the first parameter, the compiler would error out. So all functions modifying the string should take a pointer to it.

paraboul 13y ago
To be consistent between allocation and reallocation (like malloc() and realloc()). And you still want to access the old value if reallocation failed.

clarry 13y ago

Mixing signed and unsigned arithmetic operands. Not doing trivial overflow checking before arithmetic. Using results from said arithmetic as indices or starting points for memory writes. My gut says that any application using this library to process untrusted input is exploitable. Of course, it was never advertised as being secure :-) Which is unusual, as many "better strings" libraries make claims about the security of the traditional way of string handling (and then go on to do it wrong). Edit: To give a concrete example, someone here recommended BString just a few days ago. That library has a "security statement" in which it claims to prevent overflow type attacks by using signed integers instead of size_t, and then checking whether the result is negative after arithmetic. But signed overflow is undefined behavior in C, and these are not guaranteed to wrap around. And yes such things have been exploited. I don't know how likely or easy bstring is to "own" but in any case it's doinnit wrong. And yes I checked the code, it does what it claims to do..

adobriyan 13y ago
> prevent overflow type attacks by using signed integers instead of size_t, and then checking whether the result is negative after arithmetic Whoa! As if checking for overflow with unsigned is impossible...
antirez 13y ago
Hello clarry, I don't think there are APIs that if not grossly misused will lead to security issues in general. There is one issue I'm aware of that perhaps is not easily exploitable but surely is unexpected behavior, that is, overflow when you reach a 2GB string: that requires a check in sdsMakeRoomFor() for sure. Note that this could be fixed by using uint64_t type for example in the header, however in the original incarnation of SDS inside Redis this was not possible for memory usage concerns. In the standalone library I believe it is instead a great idea, since 2GB is no longer an acceptable limit. From the point of view of the security the most concerning function looks like sdsrange(), there are sanity checks in place to avoid that indexes received from the outside can lead to issues, but I'll do a security review in the future in order to formally check for issues.
- 13y ago

vvde 13y ago

Making sds a typedef for char* is very convenient. But it makes it very easy to pass an sds to a function that expects a C string without checking for null bytes. Ruby, Java, Perl, PHP have all had security problems when interacting with C because they failed to properly distinguish binary-safe strings and C strings. http://insecure.org/news/P55-07.txt http://insecure.org/news/P55-07.txt http://cwe.mitre.org/data/definitions/626.html http://cwe.mitre.org/data/definitions/626.html

kzrdude 13y ago
I'd prefer a typesafe version (that would be a library with a struct type). It could even be a trivial wrapper struct for the char *.

oh_sigh 13y ago

In the case of disadvantage #1: s = sdscat(s,"Some more data"); You could fix that by adding a "remote pointer" header field. Inside of sdscat, you would allocate a new sds struct, and set the remote pointer header field in `s` to the new sds structs location. You could also try to do a realloc and maybe youll get the same starting pointer back again.

sdegutis 13y ago

My biggest gripe with C's string functions is that it's really easy to make off-by-one errors when trying to do anything with two strings, due to NUL and the way they seem to handle it inconsistently. I'm constantly having to check the docs for any given string function to find out how it handles NUL (which isn't always in an obvious spot thanks to the design of man pages). And once I've found it, I have to come up with some contrived example that usually needs to be written in a comment just to make sure I've used its intended algorithm correctly and didn't cause an off-by-one error. If this library hides all that for me, I'm sold.

mbreese 13y ago

How much better is this dynamic approach than something like immutable strings? (not that char* is immutable) Since with the sds library, you could potentially be getting back a new pointer for each operation, you could just as easily be working from an immutable string library. Do immutable strings have poor performance? I've never really considered it.

wildmXranat 13y ago

I remember lifting the 'sds' string implementation from within the redis back in the day. Thanks antirez

codys 13y ago

ustr [1] is another library to consider. It uses a variable sized header to avoid having large (percentage wise) overhead for short strings. 1: http://www.and.org/ustr/ http://www.and.org/ustr/

acqq 13y ago

The CString C++ class from Microsoft's MFC and now also ATL used since forever the trick of having both the length and the reference counting in the single allocation with the characters themselves, as well as additional 0-termination character even if it was initialized with non-zero terminated character.

wereHamster 13y ago

How does it compare to strbuf that is used in git?