Date: Wed, 12 Dec 2001 10:36:19 -0800 From: Terry Lambert <tlambert2@mindspring.com> To: Andrea Campi <andrea@webcom.it> Cc: Bakul Shah <bakul@bitblocks.com>, freebsd-arch@FreeBSD.ORG Subject: Re: Real world Root Resizing (was Re: Proposed auto-sizing patch ... Message-ID: <3C17A3A3.A439BE21@mindspring.com> References: <200112092050.PAA26830@glatton.cnchost.com> <20011212162203.GA9595@webcom.it>
next in thread | previous in thread | raw e-mail | index | archive | help
This comes up once in a while, so it's worth treating, once in a while... Andrea Campi wrote: > #include <std/disclaimer> > > I was able to simple boot to single user and growfs my / without any magic. > I *might* have changed it to read-only just for safety but I don't think so. > After that of course I rebooted immediately... You either had spare space afterward, or you shrunk your swap to accommodate the increase (or your swap is writing to it now 8^(). Note that growing the FS doesn't entirely do what you think it does. If your FS was 90% full on average, then each of your cylinder groups was 90% full on average. Now say you had 99 cylinder groups, and you added one cylinder group. Your new cylinder group is 0% fiull, and the rest are 90% full. What is the probability that the new cylinder group will be selected for new writes? The answer is 1%. Ideally, you would want to weight the choice based on how full each cylinder group was, but that won't happen, since it defeats the seek optimization if you do that. So your disk fragmentation is still there... your disks start fragmenting at over 85% full, since the space selection function is feectively a hash, and, as we learned in CS 201 when we first read Knuth's book on Seminumerical Algorithms: Sorting and Searching, after 85% hash fill, you will start to get collisions, even with a perfect hash, given fullt random input data. I think that a 4M cylinder group would be reasonable; you could add cylinder groups as you deem fit, and run the system on top of virtual partitions made up of free disk space (what AIX calls "PP"'s -- Physical Partitions). But you will have fragmentation problems, because of the selection mechanism used by UFS. So lets try another less drastic one: my disk is 90% full, and so is 8% fragmented (on average, this is about what it will be). I double the disk size. Now it's 4% fragmented. Now as time goes on, I have a 50/50 chance of allocating in the new (free) area, or allocating in the old area. Allocations in the old area will continue to increase fragmentation. What went wrong? Really, as part of growing an FS, you need to defragment it, so that the average fill percentage of all cylinder groups is equal. That way, as you go forward, the allocation will be approximately equal across all cylinder groups (since that's how the allocation works), and you will maintain a uniform level of fragmentation going forward. You could imagine a brute force tool to do this: back up to tape, newfs, and restore from tape. A better tool would allow you to defragment an existing FS, or even run in the background at boot, and defragment only if necessary (some inequality threshold on per cylinder group fill amounts, perhaps). An even better tool might allow you to "defragment" a large disk, at the same time declaring the end of that disk "off limits". Doing that would let you actually free up cylinder groups at the end of a disk -- and shrink partitions, as well as expand them. So, to make this relevent to -arch: a good junior FS hacker project would be to write a defragmentation tool. Before you start, realize that if you use FFS partitions the way you are supposed to, no one will ever need your tool. But if you fill up and then clean out the unused files at very close to a full disk, or you grow, or (if your new tool is smart enough) shrink partitions, then people would find your tool useful. Bonus points: make the code general enough, and encapsulate state well enough, that someone could use the code in a third party tool, or could use it to resize two FFS partitions simultaneously. Bonus bonus points: send the source code to this tool to the "Power Quest" people for inclusion in the next release of "Partition Magic", so that FreeBSD is represented there, and not just Linux. -- Terry To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-arch" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?3C17A3A3.A439BE21>