Re: ProDOS Directory

[dempson@actrix.gen.nz (David Empson)]

ground.ecn AppleII Librarian <apple2pd@ground.ecn.uiowa.edu> wrote:

> Subdirs do have a finite limit, but it is rather large.  13 entries/block
> and a subdir can grow from seedling to sapling and I presume tree file.

Nope.  Subdirectories don't use the seedling/sapling/tree model - they
are a separate storage type, and are implemented as a simple linked
list.

The theoretical limit on the number of entries in a ProDOS subdirectory
is determined by the maximum size of the volume: 65535 blocks, minus
overhead required for the boot blocks, root directory and volume bitmap.

For a 65535 block volume, there are 65536 bits in the volume bitmap,
which is 8KB, or 16 blocks.  Assuming a standard root directory (4
blocks), this means a total fixed volume overhead of 16 + 4 + 2 = 22
blocks, leaving 65535 - 22 = 65513 blocks for subdirectories and files.

Assuming you have a single subdirectory in the root directory, and the
subdirectory is filled with the maximum possible number of single block
(seedling) files: the first subdirectory block can refer to 12 files at
one block each, plus one block for the subdirectory. Each subsequent
subdirectory block can refer to 13 files at one block each, plus one
block for the subdirectory.

Allowing for the first subdirectory block, we have 13 blocks used and 12
files, leaving 65500 blocks free.  Divide this by 14 (rounding down) to
get the number of complete subdirectory blocks (along with 13 files).

INT(65500 / 14) = 4678

4678 * 14 = 65492, so we have 8 blocks left, allowing one more
subdirectory blocks and 7 more files.

Totals:

4680 blocks for the subdirectory

12 + 4678 * 13 + 7 = 60833 files in the subdirectory (and 6 unused
entries).

It would be difficult to create a larger subdirectory without cheating
(direct block writes), because ProDOS always reuses entries for deleted
files before it will allocate new entries at the end of the directory.
The only way to get more files would be if you could create a directory
entry that referenced a file which occupied zero blocks, and I can't
think of any storage type which supports such a file.

> So, a ProDOS pgm or utility which assumes 13 entries/block and a 4 block
> volume directory is wrong.  It should determine this from the volume
> header and not assume the usual 4&13.

It shouldn't even assume the subdirectories are the same as the root
directory - each subdirectory repeats the entry length and entries per
block fields.

> In summary, 12 files for /RAM, 51 files for /anyp8vol, and 32767 or so
> files for subdirs is usual.  But ProDOS file system is flexible and these
> limits are easily changed, except for the 32768 block volume size.

Incidentally, the maximum ProDOS volume size is 65535 blocks (32767.5
KB), not 32768 blocks.

(You could theoretically have a volume containing 65536 blocks, with
block numbers ranging from 0x0000 to 0xFFFF, but it would be problematic
because the total block count cannot be represented in a 16 bit number.)

-- 
David Empson
dempson@actrix.gen.nz