About :: TODO :: Blog :: RSS :: Old blog :: Projects :: GIT :: Gallery :: Notes

Tue, 14 Nov 2006

Delayed allocation and fragmentation.


Quotation from Andreas Dilger:

Essentially, delaying the disk allocation until a file is large/complete
(delalloc) and then using a buddy allocator in memory to get contiguous
chunks of disk is better than hard 64K+ cluster because it avoids
internal fragmentation and allows much more optimal/efficient placement
than just a factor of 16 reduction in the block count.

/devel/fs :: Link / Comments (0)

Why trees are better than binary search.


For netchannels wildcard support I need to create set of non-crossing intervals which will be examined for each packet. It is possible to put them one-by-one and thus form an array of intervals which can be traversed using binary search, but there is a major problem when we will add new interval, which should be placed somewhere inside the existing array - that will force array reallocation and copy. This problem also applies to hash tables and actually all other table-based approaches, but does not exist in trees, although tree requres a bit more memory.
both have the same search speed about O(log2(N)), where N is number of intervals.

Rough code snippet (no return value checks and reference counters update), which splits intervals into non-crossing ranges:

	if (in->min < new->min) {
		netchannel_interval_split(in, in->min, new->min-1, GFP_KERNEL);
		if (in->max > new->max) {
			netchannel_interval_split(NULL, new->min, new->max, GFP_KERNEL);
			netchannel_interval_split(new, new->max+1, in->max, GFP_KERNEL);
		} else if (in->max < new->max) {
			netchannel_interval_split(NULL, new->min, in->max, GFP_KERNEL);
			netchannel_interval_split(new, in->max+1, new->max, GFP_KERNEL);
		} else {
			netchannel_interval_split(new, new->min, in->max, GFP_KERNEL);
		}
	} else if (in->min > new->min) {
		netchannel_interval_split(in, new->min, in->min-1, GFP_KERNEL);
		if (in->max > new->max) {
			netchannel_interval_split(NULL, in->min, new->max, GFP_KERNEL);
			netchannel_interval_split(new, new->max+1, in->max, GFP_KERNEL);
		} else if (in->max < new->max) {
			netchannel_interval_split(NULL, in->min, in->max, GFP_KERNEL);
			netchannel_interval_split(new, in->max+1, new->max, GFP_KERNEL);
		} else {
			netchannel_interval_split(new, in->min, new->max, GFP_KERNEL);
		}
	} else {
		if (in->max > new->max) {
			netchannel_interval_split(in, in->min, new->max, GFP_KERNEL);
			netchannel_interval_split(new, new->max+1, in->max, GFP_KERNEL);
		} else if (in->max < new->max) {
			netchannel_interval_split(in, in->min, in->max, GFP_KERNEL);
			netchannel_interval_split(new, in->max+1, new->max, GFP_KERNEL);
		} else {
			netchannel_interval_split(in, in->min, in->max, GFP_KERNEL);
		}
	}

/devel/networking :: Link / Comments (0)

Filesystem stress testing and emulation tool.


I wonder why Linux does not have FS stress testing and emulation tool like netem for network, which allows to perform drop, corruption, reordering, duplication and other interesting options extremely usefull for protocol testing.

Consider the same tool which works under FS layer, for example as ATA/SCSI controller, which can perform various message mangling, delaying, reordering and other features emulating incorrect behaviour of the hardware. It can even send data down to the real hard drive, thus emulating even various software conditions like scheduling starvation, irq storms and so on.

I think such tool is a must for fs development and should be implemented at least in parallel or even before various userlevel stress tools are started to stress the filesystem.

This deserves entry in TODO list.

/devel/fs :: Link / Comments (0)

Do you know what Google Earth lacks at the first place?


No, not 3d buildings - it lacks ion cannon.

/other :: Link / Comments (0)