[9fans] Rstat needs three size fields?

[9fans] Rstat needs three size fields?

[Sam]

I'm having some trouble rationalizing the extra
two byte size as documented in stat(5) BUGS.  I
see how having size[2] as part of the stat layout
helps in parsing multiple directory entries
end-to-end in a read(5).  Where I'm stuck is
why it's more consistent to add another one.

If the argument were, ``while we could elide
the size[2] field from the stat layout because
the length of the remainder of the message is known,
we leave it in for consistency with directory reads''
I would understand.

What am I missing here?

Sam

Re: [9fans] Rstat needs three size fields?

[ron minnich]

On Mon, 30 Jun 2003, Sam wrote:

> I'm having some trouble rationalizing the extra
> two byte size as documented in stat(5) BUGS.  I
> see how having size[2] as part of the stat layout
> helps in parsing multiple directory entries
> end-to-end in a read(5).  Where I'm stuck is
> why it's more consistent to add another one.

well it confused me too in v9fs but once I saw what was going on it
actually makes a kind of sense to me.

ron

Re: [9fans] Rstat needs three size fields?

[boyd, rounin]

is it not because of?

    A read of a directory yields an integral number of directory entries in
    the machine independent encoding given above (see read(5)).

glueing partial directory entries back together is no fun.

Re: [9fans] Rstat needs three size fields?

[Russ Cox]

> I'm having some trouble rationalizing the extra
> two byte size as documented in stat(5) BUGS.  I
> see how having size[2] as part of the stat layout
> helps in parsing multiple directory entries
> end-to-end in a read(5).  Where I'm stuck is
> why it's more consistent to add another one.

The variable length fields in 9P2000 always have
a two-byte length in front of them.  So does the
stat buffer.

	Tstat tag[2] stat[n]

parses as you would expect given the notational
conventions.

Russ

Re: [9fans] Rstat needs three size fields?

[Sam]

> The variable length fields in 9P2000 always have
> a two-byte length in front of them.  So does the
> stat buffer.

Oh, I see.  That does make sense.  Thank you.

I failed to make the connection that the stat
buffer itself is considered a variable length
field (including the size).

One last niggle -- intro(5), paragraph 4, sentence 3
could stand to have "of larger or" removed since
the 13 byte w?qid doesn't have a two-byte size.

Just curious, but why isn't data in Rread and Twrite
a variable length field with a two-byte count?  Count was
two bytes in 2nd Ed 9P; what was the motivating push
for four bytes?

I suppose it does allow you to reserve count values
~0 through ~0-6 for special meaning, though this seems
unexploited.

Cheers,

Sam

Re: [9fans] Rstat needs three size fields?

[rob pike, esq.]

> Just curious, but why isn't data in Rread and Twrite
> a variable length field with a two-byte count?  Count was
> two bytes in 2nd Ed 9P; what was the motivating push
> for four bytes?

65536 is not a very big number in modern i/o systems.

-rob

Re: [9fans] Rstat needs three size fields?

[Douglas A. Gwyn]

rob pike, esq. wrote:
> 65536 is not a very big number in modern i/o systems.

Actally neither is 2^32.
What the world needs is an efficient variable-length
encoding of unsigned integers.

Re: [9fans] Rstat needs three size fields?

[Geoff Collyer]

Actually 2⁳⁲ is a fairly big number in the context of 9P read &
write byte counts (which is what Rob was talking about).  I don't
think I've ever read or written 4,294,967,296 bytes (or even close to
that many) in a single operation.

As for efficient integer encodings, at least for this purpose, if we
restricted I/O transfer lengths to powers of 2, we could just supply
the exponent in 9P (e.g., 16 in a length field in 9P would represent
2ⁱ⁶=65,536). ☺  We could get away with a single byte for length fields,
even a signed byte.

Re: [9fans] Rstat needs three size fields?

[Douglas A. Gwyn]

Geoff Collyer wrote:
> Actually 2�� is a fairly big number in the context of 9P read &
> write byte counts (which is what Rob was talking about).  I don't
> think I've ever read or written 4,294,967,296 bytes (or even close to
> that many) in a single operation.

It's not what you have done in the past, but what somebody might
reasonably want to do in the foreseeable future.  4GB is no longer
unimaginably large, even for main RAM size, nor does it take a
ridiculous amount of time to transfer it among hosts in modern
networks.  In my opinion we ought to be able to access the
entirety of any given object without having to artificially
segment it.

> As for efficient integer encodings, at least for this purpose, if we
> restricted I/O transfer lengths to powers of 2, we could just supply
> the exponent in 9P ...

The trouble is that even if the user accepted the power-of-two
restriction, this would waste about 50% of the channel bandwidth.

What I had in mind was something like Ken Thompson once devised,
a variable-length integer format.  Without built-in language
support, though, this tends to bog down computation.  It seems
there should be some nice balance between computability and
flexibility..

Re: [9fans] Rstat needs three size fields?

[ron minnich]

Or keep it simple and in 9p2001 just grow it to 64 bits. Seems to me
that's what the version field can buy you.

ron

Re: [9fans] Rstat needs three size fields?

[rob pike, esq.]

> As for efficient integer encodings, at least for this purpose, if we
> restricted I/O transfer lengths to powers of 2, we could just supply
> the exponent in 9P (e.g., 16 in a length field in 9P would represent
> 2ⁱ⁶=65,536). ☺  We could get away with a single byte for length fields,
> even a signed byte.

and when you issued a 2^10 byte read and receive 318 bytes back,
how would you represent the return count?

-rob

Re: [9fans] Rstat needs three size fields?

[boyd, rounin]

> and when you issued a 2^10 byte read and receive 318 bytes back,
> how would you represent the return count?

that's the problem.  2^16 and 2^32 are no longer large numbers, but
you can't expect the read return to be a power of two.

simple, sufficient protocols are the way to go -- much as i am contrary ...

Re: [9fans] Rstat needs three size fields?

[rog]

> simple, sufficient protocols are the way to go -- much as i am contrary ...

sufficient for what?

Re: [9fans] Rstat needs three size fields?

[boyd, rounin]

> sufficient for what?

sufficient to do the job.   everything is a trade-off ...

[9fans] simple, sufficient

[rog]

> > sufficient for what?
>
> sufficient to do the job.   everything is a trade-off ...

there are many different jobs...

some might even require >4GB unit transfer sizes to accomplish
the job efficiently enough.

for another, maybe 9p2000's extra 8 byte overhead on a Tread compared
to old 9p might make a crucial difference.

"simple and sufficient" is a platitude: i don't think anyone really
wants to introduce complexity for its own sake, and what's the point
in implementing something if it's not sufficient for the task you want
to solve?

what i think we're really after is... simple and *insufficient*; :-)
choose the things you *won't* be able to do (e.g.  read >4GB in a
chunk, associate arbitrary metadata on a file) in order to gain
simplicity overall.

isn't this the reason for plan 9's beauty, and conversely perhaps, one
reason for its lack of popularity?

trade-offs (particularly trade-offs involving the sacrifice of some
potential feature in return for ill-defined simplicity) are hard.
many people are unwilling to make them; hence endlessly increasing
bloat.

Re: [9fans] Rstat needs three size fields?

[Geoff Collyer]

> and when you issued a 2^10 byte read and receive 318 bytes back, >
> how would you represent the return count?

It was a joke suggestion, but obviously only the length fields in the
requests could be encoded as binary logarithms, the responses would
need ordinary integer length fields not only for short reads (and
writes, in error cases) but to represent values such as 0 and -1.

Clearly, simple protocols are the right way to go.

Re: [9fans] Rstat needs three size fields?

[William Josephson]

On Mon, Jul 07, 2003 at 02:03:08AM -0700, Geoff Collyer wrote:
> As for efficient integer encodings, at least for this purpose, if we
> restricted I/O transfer lengths to powers of 2, we could just supply
> the exponent in 9P (e.g., 16 in a length field in 9P would represent
> 2??????=65,536). ???  We could get away with a single byte for length fields,
> even a signed byte.

Bad Idea(tm)  (think Ethernet MTU; this particular
brain-damage has been tried ;-)

Re: [9fans] Rstat needs three size fields?

[rob pike, esq.]

>> 65536 is not a very big number in modern i/o systems.
>
> Actally neither is 2^32.

sometimes you become boyd-like in your contrarianism.
2^32 is a huge block size, even today, while 2^16 is not.
hence the increase in the field.

> What the world needs is an efficient variable-length
> encoding of unsigned integers.

not as much as it needs simple protocols.

-rob

Re: [9fans] Rstat needs three size fields?

[Jack Johnson]

rob pike, esq. wrote:

>>What the world needs is an efficient variable-length
>>encoding of unsigned integers.
>
> not as much as it needs simple protocols.

I keep getting stuck on, you know, world peace.

How's that for a simple protocol.

-Jack

Re: [9fans] Rstat needs three size fields?

[Douglas A. Gwyn]

"rob pike, esq." wrote:
> >> 65536 is not a very big number in modern i/o systems.
> > Actally neither is 2^32.
> sometimes you become boyd-like in your contrarianism.
> 2^32 is a huge block size, even today, while 2^16 is not.

Perhaps I'm getting tired of engineers always tweaking
size fields up by a small amount every time they become
too small.  If you've had to deal with large IDE drives
on BIOSes more than a couple of years old you know what
I mean.  Ever-increasing-size FAT filesystem formats are
another example.  Utility software that is even slightly
old keeps turning out to be unable to cope with new
developments, due mainly to inadequate bits in existing
formats.  Why should there be such a drain on developer
resources to continually adapt to changing formats when
we could do it right for once and for all?

My rule of thumb used to be that whatever the biggest
size you can imagine for some object, allocate twice
as many bits to hold its size as seem sufficient.  But
even that approach doesn't survive for the decades that
ought to be attainable for things like disk descriptors.

Re: [9fans] Rstat needs three size fields?

[boyd, rounin]

> My rule of thumb used to be that whatever the biggest
> size you can imagine for some object, allocate twice
> as many bits to hold its size as seem sufficient.

as a reallocation strategy i take what i have and then double it.
this is when i'm dealing with something that's going to 'grow'
and i don't want to have to realloc for each new 'element'.

Re: [9fans] Rstat needs three size fields?

[matt]

boyd, rounin wrote:

>>My rule of thumb used to be that whatever the biggest
>>size you can imagine for some object, allocate twice
>>as many bits to hold its size as seem sufficient.
>>
>>
>
>as a reallocation strategy i take what i have and then double it.
>this is when i'm dealing with something that's going to 'grow'
>and i don't want to have to realloc for each new 'element'.
>

I've recently had this challenge and was wodnering what people use as a
resize strategy

I've read and seen the double it but decided it was pretty likely to run
out of memory. Allocating 200Mb of memory for one extra array index
seemed a bit risky.

I plucked 5 + 125% as a compromise (the 5 for a performance boost the
the beginning)

Someone must have done some reseach into it but google isn't being very
helpful

In the end I used the "make a list and when you're done, count the
elements and make the array" strategy

Re: [9fans] Rstat needs three size fields?

[Dan Cross]

matt <matt@proweb.co.uk> writes:
> >as a reallocation strategy i take what i have and then double it.
> >this is when i'm dealing with something that's going to 'grow'
> >and i don't want to have to realloc for each new 'element'.
>
> I've recently had this challenge and was wodnering what people use as a
> resize strategy
>
> I've read and seen the double it but decided it was pretty likely to run
> out of memory. Allocating 200Mb of memory for one extra array index
> seemed a bit risky.
>
> I plucked 5 + 125% as a compromise (the 5 for a performance boost the
> the beginning)
>
> Someone must have done some reseach into it but google isn't being very
> helpful
>
> In the end I used the "make a list and when you're done, count the
> elements and make the array" strategy

Doubling is, I think, the most common strategy; it works well with
memory allocators based around the buddy system or variants thereof.
Another common strategy that I've used is to double up until to
threshold, and then extend by a constant chunk size after that.  For
instance, you might double things until you get to, say, a megabyte,
and then add on a megabyte after that.

As Boyd will no doubt tell you, everything is a tradeoff.  Here, I'm
trading some amount of speed for memory efficiency.  If you're using
smallish data sets, say anywhere from a couple of bytes up to a several
megabytes, it will work resonably well (it will take only 24
allocations to get 5 megabytes if you start with a nil pointer).  If
you're trying to hold several gigabytes, obviously you might want to
change around the starting size and chunk size, or adopt an entirely
different strategy.

For truly variable data sets, I like dynamic data structures that can
grow without bound in a natural way.  Many of these are simple to
implement and have other desirable properties.  For instance, lists are
just about the simplest thing one can build, and work well for linear
data sets (though have some overhead in having to maintain links; this
can be amortized by storing more than one datum in a single node in the
list).

Anyway, that's just me.

	- Dan C.

Re: [9fans] Rstat needs three size fields?

[boyd, rounin]

> Another common strategy that I've used is to double up until to
> threshold, and then extend by a constant chunk size after that.  For
> instance, you might double things until you get to, say, a megabyte,
> and then add on a megabyte after that.

yeah, that's not a bad idea, but it depends on what you're trying to
allocate etc ...  defining the 'threshold' and the 'chunk size' is the
hard part.

make a guess and then gets some stats on how it actually behaves
and then tweak the numbers.  make sure you have some good
profiling tools too, 'cos the problem might not be the memory
allocator, even though it's _the dumbest allocator ever written_.

Re: [9fans] Rstat needs three size fields?

[ron minnich]

On Tue, 8 Jul 2003, boyd, rounin wrote:

> > Another common strategy that I've used is to double up until to
> > threshold, and then extend by a constant chunk size after that.  For
> > instance, you might double things until you get to, say, a megabyte,
> > and then add on a megabyte after that.
>
> yeah, that's not a bad idea, but it depends on what you're trying to
> allocate etc ...  defining the 'threshold' and the 'chunk size' is the
> hard part.

If the stuff is files, you can depend on some things. Every time I check a
file system I find the lovely bimodal size distribution. You can start
with 32K or some nominal such size and you'll cover most of the files;
past that point things are "big" so you can start allocating reasonably
big chunks.

That's how I've done it anyways, unless I pre-computed the size.

ron

Re: [9fans] Rstat needs three size fields?

[chris]

matt@proweb.co.uk wrote:
> In the end I used the "make a list and when you're done, count the
> elements and make the array" strategy
>

So you end up needing twice the memory anyway!

Re: [9fans] Rstat needs three size fields?

[matt]

chris@hollis-locke.com wrote:

>matt@proweb.co.uk wrote:
>
>
>>In the end I used the "make a list and when you're done, count the
>>elements and make the array" strategy
>>

>>So you end up needing twice the memory anyway!
>>
>>
yes, tis true, but only temporarily

Re: [9fans] Rstat needs three size fields?

[boyd, rounin]

> yes, tis true, but only temporarily

tis true it's a god-awful algorithm.

mangle the pointer from char * to void * in this:

typedef long  msg_idx;

typedef struct
{
    msg_idx    v_count;
    msg_idx    v_size;
    msg_idx    v_incr;
    char            **v_list;
}
    vec;


echo vec.c
sed 's/.//' >vec.c <<'//GO.SYSIN DD vec.c'
-/*
- * Dynamic vector of strings.
- */
-
-#ifndef lint
-static char sccsid[] = "@(#)vec.c 1.31";
-#endif lint
-
-#include "mace.h"
-
-void
-vec_init(v, n)
-register vec *v;
-register int n;
-{
- v->v_count = 0;
- v->v_size = v->v_incr = n;
- v->v_list = (char **)salloc(n * sizeof(char *));
-}
-
-char *
-vec_str(v, s)
-register vec *v;
-register char *s;
-{
- if (v->v_count == v->v_size)
-  v->v_list = (char **)srealloc((char *)v->v_list, (int)(v->v_size +=
v->v_incr) * sizeof(char *));
-
- v->v_list[v->v_count++] = s;
-
- return s;
-}
-
-char *
-vec_cat(v, s)
-register vec *v;
-register char *s;
-{
- if (v->v_count != 0)
- {
-  register char *p;
-
-  if (v->v_list[v->v_count - 1] != NULLSTR)
-  {
-   p = concat(v->v_list[v->v_count - 1], s);
-
-   (void)free(v->v_list[v->v_count - 1]);
-   (void)free(s);
-  }
-  else
-   p = s;
-
-  return v->v_list[v->v_count - 1] = p;
- }
- else
-  return vec_str(v, s);
-}
-
-void
-vec_free(v)
-register vec *v;
-{
- register int i;
-
- for (i = 0; i < v->v_count; i++)
- {
-  if (v->v_list[i] != NULLSTR)
-   (void)free(v->v_list[i]);
- }
-
- v->v_count = 0;
- v->v_size = 0;
- v->v_incr = 0;
- (void)free((char *)v->v_list);
-}
//GO.SYSIN DD vec.c

i think that demonstrates the concept.

Re: [9fans] Rstat needs three size fields?

[rog]

> > yes, tis true, but only temporarily
>
> tis true it's a god-awful algorithm.

for the kind of thing i think matt was thinking of,
something like (limbo for brevity, i'm afraid):

	items: list of Item;
	while((item := getnextitem()) != nil)
		items = item :: items;
	a := array[len items] of Item;
	for(i := 0; items != nil; items = tl items)
		a[i++] = hd items;

the amount of data copying is only O(n); if i'd been
expanding an array, it would have been O(n log n).

that's doesn't seem bad *algorithmicly* although the heap overheads
might be bad in practise.

i confess to having used this technique before.  i'm probably missing
something crucial.

why is it a "god-awful algorithm"?

Re: [9fans] Rstat needs three size fields?

[boyd, rounin]

> why is it a "god-awful algorithm"?

because it is [unecessarily] two pass.

Re: [9fans] Rstat needs three size fields?

[rog]

> > why is it a "god-awful algorithm"?

> because it is [unecessarily] two pass.

the alternative is log n passes.

Re: [9fans] Rstat needs three size fields?

[ron minnich]

On Tue, 8 Jul 2003 chris@hollis-locke.com wrote:

>
> So you end up needing twice the memory anyway!

not for just a count pass.

ron

Re: [9fans] Rstat needs three size fields?

[Dan Cross]

> > So you end up needing twice the memory anyway!
>
> not for just a count pass.

But what are you counting?  If you store all the data in a list so
that you can find out how big to make an array (are we assuming we're
getting the data from somewhere I can do more than one pass?), you
still use twice the memory when you allocate the array.

	- Dan C.

Re: [9fans] Rstat needs three size fields?

[ron minnich]

On Tue, 8 Jul 2003, Dan Cross wrote:

> But what are you counting?  If you store all the data in a list so
> that you can find out how big to make an array (are we assuming we're
> getting the data from somewhere I can do more than one pass?), you
> still use twice the memory when you allocate the array.

I'm probably missing the point as I came into this too late, so never mind
:)

ron

Re: [9fans] Rstat needs three size fields?

[boyd, rounin]

Sam asked me:

> OK, I've been thinking about this a day now and I'm
> not sure what you mean.  There shouldn't be any partial
> directory entries, right?

in the 'old days' directories had a fixed size [2 byte inode
number + 14 byte name].  so it was easy.  you could cheat
and statically allocate and we mainly did 'cos calling malloc
was a big no-no, 'cos there was next to no memory and cpu
was scarce.

then came along BSD which gave us these lunatic long names
and a namei() that took years to fix.  so you used readdir()
and a chunk of crap because just calling read was now
_too hard_ -- in fact it was illegal.

then we had NFS.  and so you had to ask the server to send
across some number of directory entries [getdents()] and this
sat under readdir().  this was all very fine, but now you
had a bunch of library functions and system calls and NFS
protocol garbage and you couldn't use read() anymore.

in fact _the only place_ the XDR encode/decode code
existed for directory entries was _in the kernel_.  that
stuff was really 'fascinating' ...

    Brushes with death were described as "fascinating."
    To be "absolutely fascinated" meant scared witless.

        -- http://www.air-america.org/Articles/Doole.htm

should you have had ultrix and wanted to write a user-mode NFS
server you had to either get a protocol analyser, tcpdump,
dick around, guess or get hold of the code.

[i wrote an NFS version of ftpfs]

there was never anything wrong with read().  the proliferation of
crap, as a result of BSD long names, added an immense amount
of useless baggage.

should read() return partial directory entries you are in a world of
pain because you have to maintain state so that you can pick up
where you left off and try and glue the partials back together.

so the solution is to just use read() and return whole directory
entries; it simplifies things on both the client and server side.
should read return 0, multiply the malloc()'d buffer by 2, realloc()
and loop.

it helps if you have some side information so that when the read()
returns you have a clue of how much stuff is in the buffer, 'cos
buffer overruns are not your friend.

i suspect the extra size info is 'side information'.

Re: [9fans] Rstat needs three size fields?

[boyd, rounin]

Sam asked me:
> OK, I've been thinking about this a day now and I'm
> not sure what you mean.  There shouldn't be any partial
> directory entries, right?

in the 'old days' directories had a fixed size [2 byte inode
number + 14 byte name].  so it was easy.  you could cheat
and statically allocate and we mainly did 'cos calling malloc
was a big no-no, 'cos there was next to no memory and cpu
was scarce.

then came along BSD which gave us these lunatic long names
and a namei() that took years to fix.  so you used readdir()
and a chunk of crap because just calling read was now
_too hard_ -- in fact it was illegal.

then we had NFS.  and so you had to ask the server to send
across some number of directory entries [getdents()] and this
sat under readdir().  this was all very fine, but now you
had a bunch of library functions and system calls and NFS
protocol garbage and you couldn't use read() anymore.

in fact _the only place_ the XDR encode/decode code
existed for directory entries was _in the kernel_.  that
stuff was really 'fascinating' ...

    Brushes with death were described as "fascinating."
    To be "absolutely fascinated" meant scared witless.

        -- http://www.air-america.org/Articles/Doole.htm

should you have had ultrix and wanted to write a user-mode NFS
server you had to either get a protocol analyser, tcpdump,
dick around, guess or get hold of the code.

[i wrote an NFS version of ftpfs]

there was never anything wrong with read().  the proliferation of
crap, as a result of BSD long names, added an immense amount
of useless baggage.

should read() return partial directory entries you are in a world of
pain because you have to maintain state so that you can pick up
where you left off and try and glue the partials back together.

so the solution is to just use read() and return whole directory
entries; it simplifies things on both the client and server side.
should read return 0, multiply the malloc()'d buffer by 2, realloc()
and loop.

it helps if you have some side information so that when the read()
returns you have a clue of how much stuff is in the buffer, 'cos
buffer overruns are not your friend.

i suspect the extra size info is 'side information'.