Monthly Archives: September 2014

File Systems: The Semester Project – Part III

This twentieth article, which is part of the series on Linux device drivers, completes the basic simulation of a file system in user space.

<< Nineteenth Article

Till now, Shweta had implemented 4 basic functionalities of the simulated file system (sfs) browser, namely quit (browser), list (files), create (an empty file), remove (a file). Here she adds 3 little advanced functionalities to get a feel of a complete basic file system:

  • Changing permissions of a file
  • Reading from a file
  • Writing into a file

Here’s a sneak peek into her thinking process as how she came up with her implementations.

For the various command implementations, two very common requirements keep popping quite often:

  • Getting the index of the entry for a particular filename
  • Updating the entry for a given filename

Hence these two requirements, captured as the functions sfs_lookup() and sfs_update():

int sfs_lookup(int sfs_handle, char *fn, sfs_file_entry_t *fe)
{
	int i;

	lseek(sfs_handle, sb.entry_table_block_start * sb.block_size, SEEK_SET);
	for (i = 0; i < sb.entry_count; i++)
	{   
		read(sfs_handle, fe, sizeof(sfs_file_entry_t));
		if (!fe->name[0]) continue;
		if (strcmp(fe->name, fn) == 0) return i;
	}   

	return -1; 
}

void sfs_update(int sfs_handle, char *fn, int *size, int update_ts, int *perms)
{
	int i;
	sfs_file_entry_t fe;

	if ((i = sfs_lookup(sfs_handle, fn, &fe)) == -1)
	{
		printf("File %s doesn't exist\n", fn);
		return;
	}
	if (size) fe.size = *size;
	if (update_ts) fe.timestamp = time(NULL);
	if (perms && (*perms <= 07)) fe.perms = *perms;
	lseek(sfs_handle, sb.entry_table_block_start * sb.block_size +
						i * sb.entry_size, SEEK_SET);
	write(sfs_handle, &fe, sizeof(sfs_file_entry_t));
}

sfs_lookup() traverses through all the entries (skipping the invalid i.e. empty filename entries), till it finds the filename match and then returns the index and the entry of the matched entry in the function’s third parameter. It returns -1 in case of no match is found.

sfs_update() uses sfs_lookup() to get the entry and its index for the given filename. Then, it updates it back into the filesystem with: a) size, if passed (i.e. non-NULL), b) current timestamp if update_ts is set, c) permissions, if passed (i.e. non-NULL).

Changing file permissions

In the Simula file system, file permissions are basically a combination ‘rwx‘ for the user only, stored as an integer, with Linux like notation of 4 for ‘r‘, 2 for ‘w‘, 1 for ‘x‘. For changing the permissions of a given filename, sfs_update() can be used best by passing NULL pointer for size, zero for update_ts, and the pointer to permissions to change for perms. So sfs_chperm() would be as follows:

void sfs_chperm(int sfs_handle, char *fn, int perm)
{
	sfs_update(sfs_handle, fn, NULL, 0, &perm);
}

Reading a file

Reading a file is basically sequentially reading & displaying the contents of the data blocks indicated by their position from the blocks array of file’s entry and displaying that on stdout’s file descriptor 1. A couple of things to be taken care of:

  • File is assumed to be without holes, i.e. block position of 0 in the blocks array indicates no more data block’s for the file
  • Reading should not go beyond the file size. Special care to be taken while reading the last block with data, as it may be partially valid

Here’s the complete read function, keeping track of valid data using bytes left to read:

uint1_t block[SIMULA_FS_BLOCK_SIZE]; // Shared as global with sfs_write

void sfs_read(int sfs_handle, char *fn)
{
	int i, block_i, already_read, rem_to_read, to_read;
	sfs_file_entry_t fe;

	if ((i = sfs_lookup(sfs_handle, fn, &fe)) == -1)
	{
		printf("File %s doesn't exist\n", fn);
		return;
	}
	already_read = 0;
	rem_to_read = fe.size;
	for (block_i = 0; block_i < SIMULA_FS_DATA_BLOCK_CNT; block_i++)
	{
		if (!fe.blocks[block_i]) break;
		to_read = (rem_to_read >= sb.block_size) ?
						sb.block_size : rem_to_read;
		lseek(sfs_handle, fe.blocks[block_i] * sb.block_size, SEEK_SET);
		read(sfs_handle, block, to_read);
		write(1, block, to_read);
		already_read += to_read;
		rem_to_read -= to_read;
		if (!rem_to_read) break;
	}
}

Writing a file

Interestingly, write is not a trivial function. Getting data from the user through browser is okay. But based on that, free available blocks has to be obtained, filled and then their position be noted sequentially in the blocks array of the file’s entry. Typically, we do this whenever we have received a block full data, except the last block. That’s tricky – how do we know the last block? So, we read till end of input, marked by Control-D on its own line from the user – and that is indicated by a return of 0 from read. And in that case, we check if any non-full block of data is left to be written, and if yes follow the same procedure of obtaining a free available block, filling it up (with the partial data), and updating its position in the blocks array.

After all this, we have finally written the file data, along with the data block positions in the blocks array of the file’s entry. And now it’s time to update file’s entry with the total size of data written, as well as timestamp to currently modified. Once done, this entry has to be updated back into the entry table, which is the last step. And in this flow, the following shouldn’t be missed out during getting & filling up free blocks:

  • Check for no more block positions available in blocks array of the file’s entry
  • Check for no more free blocks available in the file system

In either of the 2 cases, the thought is to do a graceful stop with data being written upto the maximum possible, and discarding the rest.

Once again all of these put together are in the function below:

uint1_t block[SIMULA_FS_BLOCK_SIZE]; // Shared as global with sfs_read

void sfs_write(int sfs_handle, char *fn)
{
	int i, cur_read_i, to_read, cur_read, total_size, block_i, free_i;
	sfs_file_entry_t fe; 

	if ((i = sfs_lookup(sfs_handle, fn, &fe)) == -1) 
	{   
		printf("File %s doesn't exist\n", fn);
		return;
	}   
	cur_read_i = 0;
	to_read = sb.block_size;
	total_size = 0;
	block_i = 0;
	while ((cur_read = read(0, block + cur_read_i, to_read)) > 0)
	{   
		if (cur_read == to_read)
		{   
			/* Write this block */
			if (block_i == SIMULA_FS_DATA_BLOCK_CNT)
				break; /* File size limit */
			if ((free_i = get_data_block(sfs_handle)) == -1) 
				break; /* File system full */
			lseek(sfs_handle, free_i * sb.block_size, SEEK_SET);
			write(sfs_handle, block, sb.block_size);
			fe.blocks[block_i] = free_i;
			block_i++;
			total_size += sb.block_size;
			/* Reset various variables */
			cur_read_i = 0;
			to_read = sb.block_size;
		}
		else
		{
			cur_read_i += cur_read;
			to_read -= cur_read;
		}
	}
	if ((cur_read <= 0) && (cur_read_i))
	{
		/* Write this partial block */
		if ((block_i != SIMULA_FS_DATA_BLOCK_CNT) &&
			((fe.blocks[block_i] = get_data_block(sfs_handle)) != -1))
		{
			lseek(sfs_handle, fe.blocks[block_i] * sb.block_size,
									SEEK_SET);
			write(sfs_handle, block, cur_read_i);
			total_size += cur_read_i;
		}
	}

	fe.size = total_size;
	fe.timestamp = time(NULL);
	lseek(sfs_handle, sb.entry_table_block_start * sb.block_size +
						i * sb.entry_size, SEEK_SET);
	write(sfs_handle, &fe, sizeof(sfs_file_entry_t));
}

The last stride

With the above 3 sfs command functions, the final change to the browse_sfs() function in (previous article’s) browse_sfs.c would be to add the cases for handling these 3 new commands of chperm, write, and read.

One of the daunting questions, if it has not yet bothered you, is how do you find the free available blocks. Notice that in sfs_write(), we just called a function get_data_block() and everything went smooth. But think through how would that be implemented. Do you need to traverse all the file entry’s every time to figure out which all has been used and the remaining are free. That would be killing. Instead, an easier technique would be to get the used ones by parsing all the file entry’s, only initially once, and then keep track of them whenever more entries are used or freed up. But for that a complete framework needs to be put in place, which includes:

  • uint1_t typedef (in sfs_ds.h)
  • used_blocks dynamic array to keep track of used blocks (in browse_sfs.c)
  • Function init_browsing() to initialize the dynamic array used_blocks, i.e. allocate and mark the initial used blocks (in browse_sfs.c)
  • Correspondingly the inverse function shut_browsing() to cleanup the same (in browse_sfs.c)
  • And definitely the functions get_data_block() and put_data_block() to respectively get and put back the free data blocks based on the dynamic array used_blocks (in browse_sfs.c)

All these thoughts, incorporated in the earlier sfs_ds.h and browse_sfs.c files, along with a Makefile and the earlier formatter application format_sfs.c, are available from sfs_code.tar.bz2. Once compiled into browse_sfs and executed as ./browse_sfs, it shows up as something like in Figure 35.

Figure 35: Demo of Simula file system browser's new features

Figure 35: Demo of Simula file system browser’s new features

Summing up

As Shweta, showed the above working demo to her project-mate, he observed some miss-outs, and challenged her to find them out on her own. He hinted them to be related to the newly added functionality and ‘getting free block’ framework – some even visible from the demo, i.e. Figure 35. Can you help Shweta, find them out? If yes, post them in the comments below.

Twenty-first Article >>

   Send article as PDF   

Lists: The Building Blocks of Maxima

This twentieth article of the mathematical journey through open source, showcases the list manipulations in Maxima.

<< Nineteenth Article

Lists are the basic building blocks of Maxima. The fundamental reason being that Maxima is implemented in Lisp, the building blocks of which, are also lists.

Creation of lists

To begin with, let us walk through the ways to create a list. Simplest way to have a list in Maxima is to just define it using [ ]. So, [x, 5, 3, 2*y] is a list consisting of 4 members. However, Maxima provides two powerful functions for automatically generating lists: makelist(), create_list().

makelist() can take two forms. makelist(e, x, x0, xn) creates and returns a list using the expression e, evaluated for x using the values ranging from x0 to xn. makelist(e, x, L) – creates and returns a list using the expression e, evaluated for x using the members of the list L. Check out the example below for better clarity.

$ maxima -q
(%i1) makelist(2 * i, i, 1, 5);
(%o1)                        [2, 4, 6, 8, 10]
(%i2) makelist(concat(x, 2 * i - 1), i, 1, 5);
(%o2)                        [x1, x3, x5, x7, x9]
(%i3) makelist(concat(x, 2), x, [a, b, c, d]);
(%o3)                          [a2, b2, c2, d2]
(%i4) quit();

Note the interesting usage of concat() to just concatenate its arguments. Note that, makelist() is limited by the variation it can have – to be specific, just one – i in the first two examples, and x in the last one. If we want more, that is where the create_list() function comes into play.

create_list(f, x1, L1, …, xn, Ln) – creates and returns a list with members of the form f, evaluated for the variables x1, …, xn using the values from the corresponding lists L1, …, Ln. Here is a glimpse of its power:

$ maxima -q
(%i1) create_list(concat(x, y), x, [p, q], y, [1, 2]);
(%o1)                          [p1, p2, q1, q2]
(%i2) create_list(concat(x, y, z), x, [p, q], y, [1, 2], z, [a, b]);
(%o2)              [p1a, p1b, p2a, p2b, q1a, q1b, q2a, q2b]
(%i3) create_list(concat(x, y, z), x, [p, q], y, [1, 2, 3], z, [a, b]);
(%o3)    [p1a, p1b, p2a, p2b, p3a, p3b, q1a, q1b, q2a, q2b, q3a, q3b]
(%i4) quit();

Note the “all possible combinations” being created using the values for the variables x, y, z.

Once we have lists created, Maxima provides a host of functions to play around with them. Let’s take a walk through them.

Testing the lists

The following set of functions demonstrates the various checks on lists:

  • atom(v) – returns true if v is an atomic element, false otherwise
  • listp(L) – returns true if L is a list, false otherwise
  • member(v, L) – returns true if v is a member of list L, false otherwise
  • some(p, L) – returns true if predicate p is true for at least one member of list L, false otherwise
  • every(p, L) – returns true if predicate p is true for all members of list L, false otherwise
$ maxima -q
(%i1) atom(5);
(%o1)                                true
(%i2) atom([5]);
(%o2)                                false
(%i3) listp(x);
(%o3)                                false
(%i4) listp([x]);
(%o4)                                true
(%i5) listp([x, 5]);
(%o5)                                true
(%i6) member(x, [a, b, c]);
(%o6)                                false
(%i7) member(x, [a, x, c]);
(%o7)                                true
(%i8) some(primep, [1, 4, 9]);
(%o8)                                false
(%i9) some(primep, [1, 2, 4, 9]);
(%o9)                                true
(%i10) every(integerp, [1, 2, 4, 9]);
(%o10)                               true
(%i11) every(integerp, [1, 2, 4, x]);
(%o11)                               false
(%i12) quit();

List recreations

Next, is a set of functions operating on list(s) to create and return new lists:

  • cons(v, L) – returns a list with v followed by members of L
  • endcons(v, L) – returns a list with members of L followed by v
  • rest(L, n) – returns a list with members of L, except the first n members (if n is non-negative), otherwise except the last -n members. n is optional, in which case, it is taken as 1.
  • join(L1, L2) – returns a list with members of L1 and L2 interspersed
  • delete(v, L, n) – returns a list like L but with the first n occurences of v, deleted from it. n is optional, in which case all occurences of v are deleted
  • append(L1, …, Ln) – returns a list with members of L1, …, Ln, one after the other
  • unique(L) – returns a list obtained by removing the duplicate members in the list L
  • reverse(L) – returns a list with members of the list L in reverse order
$ maxima -q
(%i1) L: makelist(i, i, 1, 10);
(%o1)                   [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
(%i2) cons(0, L);
(%o2)                 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
(%i3) endcons(11, L);
(%o3)                 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
(%i4) rest(L);
(%o4)                    [2, 3, 4, 5, 6, 7, 8, 9, 10]
(%i5) rest(L, 3);
(%o5)                       [4, 5, 6, 7, 8, 9, 10]
(%i6) rest(L, -3);
(%o6)                        [1, 2, 3, 4, 5, 6, 7]
(%i7) join(L, [a, b, c, d]);
(%o7)                      [1, a, 2, b, 3, c, 4, d]
(%i8) delete(6, L);
(%o8)                    [1, 2, 3, 4, 5, 7, 8, 9, 10]
(%i9) delete(4, delete(6, L));
(%o9)                      [1, 2, 3, 5, 7, 8, 9, 10]
(%i10) delete(4, delete(6, join(L, L)));
(%o10)        [1, 1, 2, 2, 3, 3, 5, 5, 7, 7, 8, 8, 9, 9, 10, 10]
(%i11) L1: rest(L, 7);
(%o11)                            [8, 9, 10]
(%i12) L2: rest(rest(L, -3), 3);
(%o12)                           [4, 5, 6, 7]
(%i13) L3: rest(L, -7);
(%o13)                             [1, 2, 3]
(%i14) append(L1, L2, L3);
(%o14)                  [8, 9, 10, 4, 5, 6, 7, 1, 2, 3]
(%i15) reverse(L);
(%o15)                   [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
(%i16) join(reverse(L), L); 
(%o16)   [10, 1, 9, 2, 8, 3, 7, 4, 6, 5, 5, 6, 4, 7, 3, 8, 2, 9, 1, 10]
(%i17) unique(join(reverse(L), L)); 
(%o17)                   [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
(%i18) L;
(%o18)                   [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
(%i19) quit();

Note that the list L is still not modified. For that matter, even L1, L2, L3 are not modified. In fact, that is what is meant by that all these functions recreate new modified lists, rather than modifying the existing ones.

List extractions

Here goes a set of functions extracting the various members of a list. first(L), second(L), third(L), fourth(L), fifth(L), sixth(L), seventh(L), eight(L), ninth(L), tenth(L) – respectively return the first, second, … member of the list L. last(L) – returns the last member of the list L

$ maxima -q
(%i1) L: create_list(i * x, x, [a, b, c], i, [1, 2, 3, 4]);
(%o1)       [a, 2 a, 3 a, 4 a, b, 2 b, 3 b, 4 b, c, 2 c, 3 c, 4 c]
(%i2) first(L);
(%o2)                                  a
(%i3) seventh(L);
(%o3)                                 3 b
(%i4) last(L);
(%o4)                                 4 c
(%i5) third(L); last(L);
(%o5)                                 3 a
(%o6)                                 4 c
(%i7) L;
(%o7)       [a, 2 a, 3 a, 4 a, b, 2 b, 3 b, 4 b, c, 2 c, 3 c, 4 c]
(%i8) quit();

Again, note that the list L is still not modified. But, why have we been talking of that? To bring out the fact, that we may need to modify the existing lists, and none of the above functions would do that. Note that, we may achieve that by assigning the return values of the various list recreation functions back to the original list. However, there are few functions, which does that right away.

List manipulations

The following are the two list manipulating functions provided by Maxima:

  • push(v, L) – inserts v at the beginning of the list L
  • pop(L) – removes and returns the first element from list L

Note that L must be a symbol bound to a list, not the list itself, in both the above functions, for them to modify it. Also, these functionalities are not available by default, so we need to load the basic Maxima file. Check out the demonstration below.

We may display L after doing these operations, or even check the length of L to verify the actual modification of L. And, in case we need to preserve a copy of the list, function copylist() can be used, as such.

$ maxima -q
(%i1) L: makelist(2 * x, x, 1, 10);
(%o1)                [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
(%i2) push(0, L); /* This doesn't work */
(%o2)            push(0, [2, 4, 6, 8, 10, 12, 14, 16, 18, 20])
(%i3) pop(L); /* Nor does this work */
(%o3)              pop([2, 4, 6, 8, 10, 12, 14, 16, 18, 20])
(%i4) load(basic); /* Loading the basic Maxima file */
(%o4)           /usr/share/maxima/5.24.0/share/macro/basic.mac
(%i5) push(0, L); /* Now, this works */
(%o5)               [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
(%i6) L;
(%o6)               [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
(%i7) pop(L); /* Even this works */
(%o7)                                  0
(%i8) L;
(%o8)                [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
(%i9) K: copylist(L);
(%o9)                [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
(%i10) length(L);
(%o10)                                10
(%i11) pop(L);
(%o11)                                 2
(%i12) length(L);
(%o12)                                 9
(%i13) K;
(%o13)               [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
(%i14) L;
(%o14)                 [4, 6, 8, 10, 12, 14, 16, 18, 20]
(%i15) pop([1, 2, 3]); /* Actual list is not allowed */
arg must be a symbol [1, 2, 3]
#0: symbolcheck(x=[1,2,3])(basic.mac line 22)
#1: pop(l=[1,2,3])(basic.mac line 26)
 -- an error. To debug this try: debugmode(true);
(%i16) quit();

Advanced list operations

And finally, if you are still with me, here is a bonus of two sophisticated list operations:

  • sublist_indices(L, p) – returns the list indices for the members of the list L, for which predicate p is true.
  • assoc(k, L, d)L must have all its members in the form of x op y, where op is some binary operator. Then, assoc() searches for k in the left operand of the members of L. If found, it returns the corresponding right operand, otherwise d, or false, if d is missing.

Check out the demonstration below for both the above operations.

$ maxima -q
(%i1) sublist_indices([12, 23, 57, 37, 64, 67], primep);
(%o1)                              [2, 4, 6]
(%i2) sublist_indices([12, 23, 57, 37, 64, 67], evenp);
(%o2)                               [1, 5]
(%i3) sublist_indices([12, 23, 57, 37, 64, 67], oddp);
(%o3)                            [2, 3, 4, 6]
(%i4) sublist_indices([2 > 0, -2 > 0, 1 = 1, x = y], identity);
(%o4)                               [1, 3]
(%i5) assoc(2, [2^r, x+y, 2=4, 5/6]);
(%o5)                                  r
(%i6) assoc(6, [2^r, x+y, 2=4, 5/6]);
(%o6)                               false
(%i7) assoc(6, [2^r, x+y, 2=4, 5/6], na);
(%o7)                                na
(%i8) quit();

Twenty-first Article >>

   Send article as PDF