strbuf `filter' API

When crlf_to_git or ident_to_git are called "in place", the buffer already is big enough and should not be resized (as it could make the buffer address change, hence invalidate the `src' pointers !).

Also fix the growth length at the same time: we want to replace the buffer content (not append) in those functions as they are filters.

Thanks to Bernt Hansen for the bug report.

---

This patch is done on top of master, as strbuf's have been merged.
This is a major issue.

 convert.c |   12 ++++++++----
 1 files changed, 8 insertions(+), 4 deletions(-)

index 0d5e909..4664197 100644
@@ -110,7 +110,9 @@ static int crlf_to_git(const char *path, const char *src, size_t len,
 			return 0;
 	}
 
-	strbuf_grow(buf, len);
+	/* only grow if not in place */
+	if (src != buf->buf)
+		strbuf_grow(buf, len - buf->len);
 	dst = buf->buf;
 	if (action == CRLF_GUESS) {
 		/*

@@ -281,12 +283,12 @@ static int apply_filter(const char *path, const char *src, size_t len,
 		ret = 0;
 	}
 	if (close(pipe_feed[0])) {
-		ret = error("read from external filter %s failed", cmd);
+		error("read from external filter %s failed", cmd);
 		ret = 0;
 	}
 	status = finish_command(&child_process);
 	if (status) {
-		ret = error("external filter %s failed %d", cmd, -status);
+		error("external filter %s failed %d", cmd, -status);
 		ret = 0;
 	}
 

@@ -422,7 +424,9 @@ static int ident_to_git(const char *path, const char *src, size_t len,
 	if (!ident || !count_ident(src, len))
 		return 0;
 
-	strbuf_grow(buf, len);
+	/* only grow if not in place */
+	if (src != buf->buf)
+		strbuf_grow(buf, len - buf->len);
 	dst = buf->buf;
 	for (;;) {
 		dollar = memchr(src, '$', len);

1.5.3.4.207.gc79d4-dirty

---

While we're at it... Here is a stupid memory leak in apply_filter. On top of the previous commit.

 convert.c |    5 ++---
 1 files changed, 2 insertions(+), 3 deletions(-)

index 4664197..d5c197f 100644
@@ -293,10 +293,9 @@ static int apply_filter(const char *path, const char *src, size_t len,
 	}
 
 	if (ret) {
-		*dst = nbuf;
-	} else {
-		strbuf_release(&nbuf);
+		strbuf_swap(dst, &nbuf);
 	}
+	strbuf_release(&nbuf);
 	return ret;
 }
 

1.5.3.4.208.gdcc67-dirty

---

While we're at it... Here is a stupid memory leak in apply_filter. On top of the previous commit.

The same, repost, unsigned doh.

 convert.c |    5 ++---
 1 files changed, 2 insertions(+), 3 deletions(-)

index 4664197..d5c197f 100644
@@ -293,10 +293,9 @@ static int apply_filter(const char *path, const char *src, size_t len,
 	}
 
 	if (ret) {
-		*dst = nbuf;
-	} else {
-		strbuf_release(&nbuf);
+		strbuf_swap(dst, &nbuf);
 	}
+	strbuf_release(&nbuf);
 	return ret;
 }
 

1.5.3.4.208.gdcc67-dirty

* crlf_to_git and ident_to_git:

Don't grow the buffer if there is enough space in the first place. As a side effect, when the editing is done "in place", we don't grow, so the buffer pointer doesn't changes, and `src' isn't invalidated anymore.

Thanks to Bernt Hansen for the bug report.

* apply_filter:

Fix memory leak due to fake in-place editing that didn't collected the old buffer when the filter succeeds. Also a cosmetic fix.

---

This patch is on top of master, and supersedes both patch I sent before. Following dscho's remark, I only grow the buffer if they aren't big enough in the first place, which ensures that buffers are not touched if edited in place.

 convert.c |   17 ++++++++++-------
 1 files changed, 10 insertions(+), 7 deletions(-)

index 0d5e909..aa95834 100644
@@ -110,7 +110,9 @@ static int crlf_to_git(const char *path, const char *src, size_t len,
 			return 0;
 	}
 
-	strbuf_grow(buf, len);
+	/* only grow if not in place */
+	if (strbuf_avail(buf) + buf->len < len)
+		strbuf_grow(buf, len - buf->len);
 	dst = buf->buf;
 	if (action == CRLF_GUESS) {
 		/*

@@ -281,20 +283,19 @@ static int apply_filter(const char *path, const char *src, size_t len,
 		ret = 0;
 	}
 	if (close(pipe_feed[0])) {
-		ret = error("read from external filter %s failed", cmd);
+		error("read from external filter %s failed", cmd);
 		ret = 0;
 	}
 	status = finish_command(&child_process);
 	if (status) {
-		ret = error("external filter %s failed %d", cmd, -status);
+		error("external filter %s failed %d", cmd, -status);
 		ret = 0;
 	}
 
 	if (ret) {
-		*dst = nbuf;
-	} else {
-		strbuf_release(&nbuf);
+		strbuf_swap(dst, &nbuf);
 	}
+	strbuf_release(&nbuf);
 	return ret;
 }
 

@@ -422,7 +423,9 @@ static int ident_to_git(const char *path, const char *src, size_t len,
 	if (!ident || !count_ident(src, len))
 		return 0;
 
-	strbuf_grow(buf, len);
+	/* only grow if not in place */
+	if (strbuf_avail(buf) + buf->len < len)
+		strbuf_grow(buf, len - buf->len);
 	dst = buf->buf;
 	for (;;) {
 		dollar = memchr(src, '$', len);

1.5.3.4.207.gb504-dirty

This fixes it for me. Thanks!!

Bernt

I agree.

the point here is that it's in a "filter" that is called like this:

some_filter(buf->buf, buf->len, buf);
src len dst

You can call the filter with src/len being data from anywere,
including the current content of the destination buffer.

Then there is two cases, either the filter is known to be done in
place, either we can't know or we know it wont.

In the latter case, we have a bit of code like that:

      char *to_free = NULL;

      if (buf->buf == src)
	  to_free = strbuf_detach(&buf);

      .. hack ..
      free(to_free);

In the former case, then there is a small glitch, being that if we are
doing in place editing, we should not touch buffer at all (or it would invalidate "src"). If we are not in the in-place editing code though, then we have to make the resulting buffer be big enough...

Right, that would do the same btw ;)

Well, the above code is used in filters to spare reallocations. So if
we want to "blackbox" such a think, strbuf_make_room isn't the proper API. We should rather use
void *strbuf_begin_filter(struct strbuf *sb, const char *src, size_t reslen); strbuf_end_filter(void *);

strbuf_begin_filter would decide upon the hint reslen argument if
we know if we can work in place or not (has a meaning iff src points into the strbuf buffer). If not, it could stash the strbuf buffer in the returned void * to be freed at the end of the filter. It seems like a better alternative than a strbuf_make_room.

Of course, strbuf_begin_filter() would really be simple and basically
be:

    char *tmp;
    if (src points into sb->buf && reslen > sb->alloc - 1) {
        // in place editing is OK
        return NULL;
    }
    tmp = strbuf_release(&sb);
    strbuf_grow(&sb, len);
    return tmp;

and strbuf_end_filter would just be "free" :)

We could even make "reslen" be a ssize_t so that -1 would mean "I've
absolutely no idea how much space I'll need (or just in place editing is not supported). This way, both hacks I described in this mail could be hidden in the strbuf module, and be properly documented _and_ safe _and_ efficient.

What do you think ?

[Though if we do that, I still think it's more important to fix the bug in master, and have a new patch implementing this approach]

·O·  Pierre Habouzit
··O                                                [email protected]
OOO                                                http://www.madism.org

Ooookay,

I wasn't more thrilled about the previous patch than linus is. Here is
a possible API to hide the muck in the strbuf.c module, and have a way nicer to read code in convert.c.

It remais as efficient as the previous code, tries to reuse the buffer
as much as possible to avoid reallocations, and deal with even more cases (it's possible to have the "source" buffer be inside the destination strbuf now, which could sometimes help a lot).

I based this on top of master (because it's where my previous patch
was) but it should apply on next properly. It depends upon the previous patch though.

I'd say that the previous patch should go in master ASAP, and that
those two could be considered for next (having merged master in it first btw).

Cheers,

·O·  Pierre Habouzit
··O                                                [email protected]
OOO                                                http://www.madism.org

Pierre Habouzit, Fri, Oct 05, 2007 22:19:30 +0200:

They are horrible. And very specialized for these "filter" routines. To the point where I would move them into the file where they are used (convert.c only, isn't it?)

If you continue to insist the code is generic enough to justify its residence in strbuf.c, continue reading.

First off, what was wrong with dumb

    void strbuf_make_room(struct strbuf *, size_t newsize);

again?

For now they are, but moving them into convert.c is at the very least
awkward.

If newsize is >= sb->alloc then the area is reallocated, the pointer
may move, and the "src" pointer would then be invalidated.

The idea is to have a unified API to deal with both the cases where
the filtering is known not to work in place by the caller, or for the cases where it could if enough space is allocated but that a realloc is needed.

We could document it, that's not an issue.

I don't get that part. free(NULL) is totally ok.

It is detached if the filter does not works in place (caller says that
with '-1' as a hint) or if it works in place but needs a buffer reallocation.

Because the filter works on a {src, len} buffer, that points into the
buffer that we must free later in strbuf_end_filter.

but is wrong because you may just break "src". It's not the case here
because len always fits, but it's IMHO the kind of knowledge of the internals of strbufs we should not rely on.

Those are not filters, but help writing filters that would have this
prototype:

  int some_filter(const char *src, size_t len, struct strbuf *dst);

Allowing [src..src+len[ to be a subpart of `dst'. The usual semantics
of such filters is that it returns 0 if it did nothing, 1 if it wrote in dst.

This way, you can write filter_all being filter1, filter2, filter3
done one after the other this way:

int filter_all(const char *src, size_t len, struct strbuf *dst) {
    int res = 0;

    res |= filter1(src, len, dst);
    if (res) {
        src = dst->buf;
        len = dst->len;
    }
    res |= filter2(src, len, dst);
    if (res) {
        src = dst->buf;
        len = dst->len;
    }
    return res | filter3(src, len, dst);
}

Note that I did not created this semantics, it was how convert.c
worked already, in a even more convoluted way before.

·O·  Pierre Habouzit
··O                                                [email protected]
OOO                                                http://www.madism.org

Pierre Habouzit, Sun, Oct 07, 2007 16:53:55 +0200:

So what? You already _have_ to know it points inside the strbuf, so you can't expect it to be valid after any serious strbuf operation.

this just makes it convoluted and opaque (as in "not transparent")

The fact that you _have_to_ document is.

Not that. One have to store the result of start_filter and check it

Too many if's. Ugly

And why shouldn't these semantics kept to convert.c?

Then you can't write a filter, because you need to reallocate the
buffer before even starting to read the input buffer sometimes. If you reallocate the strbuf, and that your original buffer was in there, you lose.

I'm totally open to better alternatives. We could probably easily get
rid of strbuf_end_filter, as whichever way to deal with the issue I try to solve in a better way, in the end, it will always be just a "free".

So, maybe there is a way to rename strbuf_start_filter so that it's
more straightforward. The way to use the API is:

@ char *to_free = NULL;
@ if ((src is inside dst && need_realloc) || operation is not in-place)
@ to_free = strbuf_detach(dst, NULL);
@ strbuf_make_room(dst, needed_size);

    // do whatever you want with src and dst

    free(to_free);

strbuf_start_filter tries to implement the block marked with `@'. Of course:
* need_realloc == (needed_size >= dst->alloc)
* src is inside dst means:

    src > dst->buf && src < dst->buf + dst->alloc

Though, those are both things that I find ugly to "know" in convert.c. How things are allocated in strbufs is one of the few things we don't want to assume anywhere outside of the strbuf module.

Why check it ? You don't have to check. You have to keep it until
you're done with "src". Whichever the result was. The return of strbuf_start_filter intends to stash a pointer to be freed for the cases where "src" points into the destination buffer.

I missed where having this live in convert.c rather than in strbuf.c
makes it less ugly or better in any sense.

·O·  Pierre Habouzit
··O                                                [email protected]
OOO                                                http://www.madism.org

Pierre Habouzit, Sun, Oct 07, 2007 18:52:18 +0200:

Why do you have to play these games with src being inside/outside? Don't you know where src already is? AFAICS in convert.c crlf_to_git - you do. And everywhere else you know this fact too.

in convert.c it is never "inside". It is _exactly_ the ->buf. No need for generic "inside" check. Just test if src == ->buf.

And AFAICS, there is no other users of the function.

src is outside of strbuf scope. It is not internal to struct strbuf. The caller must already know if it is inside of the given strbuf instance.

need_realloc is covered by make_room, isn't it?

I'd suggest just fix the caller, it is simple in convert.c: just use ret, which contains exactly this information. If you insist on editing in-place, which makes your routines really need the in-placeability informaion. Just give it to them, better explicitely. All of this makes the routines very convert.c specific, which is the reason why I argument to have them just there and nowhere else.

Alternatively, one can memdup ->buf (as it is the input for next filter) every time a filter modifies it (which is safe, but simple, slow, requires memory, and may fragment heap):

/* simplified */
int convert_to_git(const char *path, const char *src, size_t len, struct strbuf *dst)

{
	int crlf = CRLF_GUESS;
	int ident = 0, ret = 0;
	char *filter = NULL;
	const char *tmp = src;

	ret |= apply_filter(path, tmp, len, dst, filter);
	if (ret) {
		tmp = xmemdupz(dst->buf, dst->len);
		len = dst->len;
	}

	if (crlf_to_git(path, tmp, len, dst, crlf)) {
		ret |= 1;
		if (tmp != src)
			free((void*)tmp);
		tmp = xmemdupz(dst->buf, dst->len);
		len = dst->len;
	}

	ret |= ident_to_git(path, tmp, len, dst, ident);
	if (tmp != src)
		free((void*)tmp);
	return ret;
}

It is just to show that nothing like strbuf_start_filter is _needed_ at all.

Internally yes, but make_room may move the buffer, if that happens,
there is nothing we can do, in the case where we point inside (or at the begining of - fwiw it's the same here) the buffer

This is exactly what we are trying to avoid with the current form.
Given how you try to micro-optimize strbuf_cmp I'm a bit lost here…

·O·  Pierre Habouzit
··O                                                [email protected]
OOO                                                http://www.madism.org

Pierre Habouzit, Mon, Oct 08, 2007 09:29:47 +0200:

update the outside pointer you can. But I actually lost all interest:
personally I never use the filters and deeply despise the reasons caused their existence.

I take this suggestion back. Do not use memdup, as it is slow, requires lots of memory and may fragment heap. Sorry for repeating.

I didn't. It just happened. If I _wanted_ to optimize anything I wouldn't start with a function which is used exactly one time in a program with a name like "rerere" which is not even used in default configuration.

Took a short look at strbuf.h after seeing the above code.
And I was suprised to see that all strbuf users were exposed to the strbuf structure.
Following patch would at least make sure noone fiddle with strbuf internals. Cut'n'paste - only for the example of it.
It simply moves strbuf declaration to the .c file where it rightfully belongs.

git did not build with this change....

Sam

index e33d06b..0d2d578 100644
@@ -1,6 +1,14 @@
 #include "cache.h"
 #include "strbuf.h"
 
+struct strbuf {
+       int alloc;
+       int len;
+       int eof;
+       char *buf;
+};
+
+
 void strbuf_init(struct strbuf *sb) {
        sb->buf = NULL;
        sb->eof = sb->alloc = sb->len = 0;

index 74cc012..c057be3 100644
@@ -1,11 +1,6 @@
 #ifndef STRBUF_H
 #define STRBUF_H
-struct strbuf {
-       int alloc;
-       int len;
-       int eof;
-       char *buf;
-};
+struct strbuf;
 
 extern void strbuf_init(struct strbuf *);
 extern void read_line(struct strbuf *, FILE *, int);

you're looking at an antiquated version, please look at the one in
current master on current next. In this one, what you can do or not do with the struct is explained

Of course it doesn't! people want to have direct access to ->buf and
->len, and it's definitely OK.

·O·  Pierre Habouzit
··O                                                [email protected]
OOO                                                http://www.madism.org

Understood now - thanks for the clarification.

Sam

Well, they *have* to. We want people to declare their strbufs as automatic or static structures, and using a opaque struct pointer is *not* an option (like "FILE" is doing in stdio.h).

No, following patch is fundamentally broken - it's not even a good starting point. It's bad, bad, bad.

It's also broken in another way: we want it to be really easy to use strbuf's as normal C strings.

Yes, many (totally idiotic and broken) interfaces think it's so important to "protect" their internal data structures that you have a "string_to_c()" helper function for that. That may be "good abstraction", but it's totally idiotic, because it results in horrible source code!

Tell me which is more readable:

	printf("Hello %s\n", sb->buf);

or

	printf("Hello %s\n", strbuf_to_c(sb));

and I claim that anybody who claims that the latter is "more readable" is full of shit, and has an agenda to push, so it's "more agenda-friendly" rather than readable!

So having "sb->buf" and "sb->len" be visible to users is a *good* thing. Otherwise you end up having to create millions of idiotic small helper functions, rather than just use the standard ones.

Linus

Hi Linus.

Point taken although no sane person would name it strbuf_to_c(...).

Sam

I agree with the "no sane person", but the problem is that the insane people seem to be in no short supply.

Go look at string libraries, and they all do something like that. Or worse.

- ustr: yes, it uses *exactly* what I described: "ustr_cstr()" and "ustr_len()" instead of having the data/length available easily (although it claims to do it for size reasons - perhaps valid in some cases!)

- libast: SPIF_CHARPTR_C(x). No, really.

- Vstr: doesn't have a linear data representation. Needs explicit flattening - although it appears to be something you're not ever supposed to do - it has 200+ functions to do various magic things.

- Qt (QString): QString::"data()", "ascii()" or "utf8()" or something.

At least this has the excuse of really being able to handle different locales (it didn't do that originally, though!), but they end up having a million helper functions exactly because you cannot use the normal string routines on anything!

- safesrtr, bstring: you just cast the pointer to "char *". Now *that* is classy and safe.

So there's a few sane out there, but I actually think they are in the minority (Glib, others)

Linus

I am afraid you cannot allow the direct access to the internal buffer of a string if this buffer can be implicitly shared between different instances as it is the case with QString. Because when you want to make some modification or want to get a non-const pointer to this buffer, its content has to be copied if the buffer is shared between a few copies.

On the other hand, I don't see what is the problem with using C string routines with it. ::data() returns a pointer and :capacity () returns allocated size of the buffer. ::resize() changes the size of the string. If you need a greater allocated size, you can use ::reserve(). Or did I miss something?

Dmitry

No, you didn't miss anything. Except for the fact that the original point was that it's just a damn lot simpler and more straightforward to code just using "sb->buf" for the data. IOW, go back two or three emails in the thread.

Linus

Hi,

I wonder why we resize at all if the buffer is big enough to begin with.

Ciao,
Dscho

strbuf_grow takes care of that itself but indeed you make me see that
my patch is wrong. if buf->len > len then len - buf->len is err a bit big.

I'll roll better ones.

·O·  Pierre Habouzit
··O                                                [email protected]
OOO                                                http://www.madism.org