Monthly Archives: August 2014

File Systems: The Semester Project – Part II

This nineteenth article, which is part of the series on Linux device drivers, continues with introducing the concept of a file system, by simulating one in user space.

<< Eighteenth Article

In the previous article, Shweta readied the partition on the .sfsf file by formating it with the format_sfs application. To complete the understanding of a file system, the next step in its simulation is to browse and play around with the file system created. Here is Shweta’s first-cut browser application to achieve the same. Let’s have a closer look. sfs_ds.h is the same header file, already created by Shweta.

#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <string.h>
#include <time.h>

#include "sfs_ds.h"

sfs_super_block_t sb;

void sfs_list(int sfs_handle)
{
	int i;
	sfs_file_entry_t fe;

	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;
		printf("%-15s  %10d bytes  %c%c%c  %s",
			fe.name, fe.size,
			fe.perms & 04 ? 'r' : '-',
			fe.perms & 02 ? 'w' : '-',
			fe.perms & 01 ? 'x' : '-',
			ctime((time_t *)&fe.timestamp)
			);
	}
}
void sfs_create(int sfs_handle, char *fn)
{
	int i;
	sfs_file_entry_t fe;

	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]) break;
		if (strcmp(fe.name, fn) == 0)
		{
			printf("File %s already exists\n", fn);
			return;
		}
	}
	if (i == sb.entry_count)
	{
		printf("No entries left\n", fn);
		return;
	}

	lseek(sfs_handle, -(off_t)(sb.entry_size), SEEK_CUR);

	strncpy(fe.name, fn, 15);
	fe.name[15] = 0;
	fe.size = 0;
	fe.timestamp = time(NULL);
	fe.perms = 07;
	for (i = 0; i < SIMULA_FS_DATA_BLOCK_CNT; i++)
	{
		fe.blocks[i] = 0;
	}

	write(sfs_handle, &fe, sizeof(sfs_file_entry_t));
}
void sfs_remove(int sfs_handle, char *fn)
{
	int i;
	sfs_file_entry_t fe;

	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) break;
	}
	if (i == sb.entry_count)
	{
		printf("File %s doesn't exist\n", fn);
		return;
	}

	lseek(sfs_handle, -(off_t)(sb.entry_size), SEEK_CUR);

	memset(&fe, 0, sizeof(sfs_file_entry_t));
	write(sfs_handle, &fe, sizeof(sfs_file_entry_t));
}

void browse_sfs(int sfs_handle)
{
	int done;
	char cmd[256], *fn;
	int ret;

	done = 0;

	printf("Welcome to SFS Browsing Shell v1.0\n\n");
	printf("Block size	 : %d bytes\n", sb.block_size);
	printf("Partition size : %d blocks\n", sb.partition_size);
	printf("File entry size: %d bytes\n", sb.entry_size);
	printf("Entry tbl size : %d blocks\n", sb.entry_table_size);
	printf("Entry count	: %d\n", sb.entry_count);
	printf("\n");
	while (!done)
	{
		printf(" $> ");
		ret = scanf("%[^\n]", cmd);
		if (ret < 0)
		{
			done = 1;
			printf("\n");
			continue;
		}
		else
		{
			getchar();
			if (ret == 0) continue;
		}
		if (strcmp(cmd, "?") == 0)
		{
			printf("Supported commands:\n");
			printf("\t?\tquit\tlist\tcreate\tremove\n");
			continue;
		}
		else if (strcmp(cmd, "quit") == 0)
		{
			done = 1;
			continue;
		}
		else if (strcmp(cmd, "list") == 0)
		{
			sfs_list(sfs_handle);
			continue;
		}
		else if (strncmp(cmd, "create", 6) == 0)
		{
			if (cmd[6] == ' ')
			{
				fn = cmd + 7;
				while (*fn == ' ') fn++;
				if (*fn != '')
				{
					sfs_create(sfs_handle, fn);
					continue;
				}
			}
		}
		else if (strncmp(cmd, "remove", 6) == 0)
		{
			if (cmd[6] == ' ')
			{
				fn = cmd + 7;
				while (*fn == ' ') fn++;
				if (*fn != '')
				{
					sfs_remove(sfs_handle, fn);
					continue;
				}
			}
		}
		printf("Unknown/Incorrect command: %s\n", cmd);
		printf("Supported commands:\n");
		printf("\t?\tquit\tlist\tcreate <file>\tremove <file>\n");
	}
}

int main(int argc, char *argv[])
{
	char *sfs_file = SIMULA_DEFAULT_FILE;
	int sfs_handle;

	if (argc > 2)
	{
		fprintf(stderr, "Incorrect invocation. Possibilities are:\n");
		fprintf(stderr,
			"\t%s /* Picks up %s as the default partition_file */\n",
			argv[0], SIMULA_DEFAULT_FILE);
		fprintf(stderr, "\t%s [ partition_file ]\n", argv[0]);
		return 1;
	}
	if (argc == 2)
	{
		sfs_file = argv[1];
	}
	sfs_handle = open(sfs_file, O_RDWR);
	if (sfs_handle == -1)
	{
		fprintf(stderr, "Unable to browse SFS over %s\n", sfs_file);
		return 2;
	}
	read(sfs_handle, &sb, sizeof(sfs_super_block_t));
	if (sb.type != SIMULA_FS_TYPE)
	{
		fprintf(stderr, "Invalid SFS detected. Giving up.\n");
		close(sfs_handle);
		return 3;
	}
	browse_sfs(sfs_handle);
	close(sfs_handle);
	return 0;
}

The above (shell like) program primarily reads the super block from the partition file (.sfsf by default, or the file provided from command line), and then gets into browsing the file system based on that information, using the browse_sfs() function. Note the check performed for the valid file system on the partition file using the magic number SIMULA_FS_TYPE.

browse_sfs() prints the file system information and provides four basic file system functionalities using the following commands:

  • quit – to quit the file system browser
  • list – to list the current files in the file system (using sfs_list())
  • create <filename> – to create a new file in the file system (using sfs_create(filename))
  • remove <filename> – to remove an existing file from the file system (using sfs_remove(filename))

Figure 34 shows the browser in action, using the above commands.

Figure 34: Simula file system browser output

Figure 34: Simula file system browser output

sfs_list() traverses through all the file entries in the partition and prints all the non-null filename entries – with file name, size, permissions, and its creation time stamp. sfs_create() looks up for an available (null filename) entry and then updates it with the given filename, size of 0 bytes, permissions of “rwx”, and the current time stamp. And sfs_remove() looks up for an existing file entry, having the filename to be removed, and then nullifies it. The other parts in the above code are more of basic error handling cases like invalid command in browse_sfs(), existing file name in sfs_create(), non-existing file name in sfs_remove(), etc.

Note that the above application is the first-cut one of a full-fledged application. And so the files created right now are just with the basic fixed parameters. And, there is no way to change their permissions, content, etc, yet. However, it must be clear by now that adding those features is just a matter of adding commands and their corresponding functions, which would be provided for a few more interesting features by Shweta as she further works out the details of the browsing application.

Summing up

Once done with the other features as well, the next set of steps would take the project duo further closer to their final goals. Watch out for who takes charge of the next step of moving the file system logic to the kernel space.

Twentieth Article >>

   Send article as PDF   

Advanced Set Theory

This nineteenth article of the mathematical journey through open source, explores the advanced set theory concepts through Maxima.

<< Eighteenth Article

With the introduction to set theory fundamentals in the previous article, we are all set to explore the advanced realms of set theory through Maxima.

More set operations

We have already worked out the basic set creation techniques and some basic set operations provided by Maxima. Here are some next-level ones provided by Maxima:

  • makeset(expr, vars, varslist) – Sophisticated set creation using expressions
  • adjoin(x, S) – Returns a set with all elements of S and the element x
  • disjoin(x, S) – Returns a set with all elements S but without element x
  • powerset(S) – Returns the set of all subsets of S
  • subset(S, p) – Returns the subset of S, elements of which satisfy the predicate p
  • symmdifference(S1, S2) – Returns the symmetric difference between the sets S1 and S2, i.e. the elements in S1 or S2 but not in both

And here goes a demonstration of each one of them:

$ maxima -q
(%i1) makeset(a+b, [a, b], [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6]]);
(%o1)                          {3, 5, 7, 9, 11}
(%i2) makeset(a-b, [a, b], [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6]]);
(%o2)                                {- 1}
(%i3) makeset(a*b, [a, b], [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6]]);
(%o3)                         {2, 6, 12, 20, 30}
(%i4) makeset(a + 2*a*b + b, [a, b], [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6]]);
(%o4)                         {7, 17, 31, 49, 71}
(%i5) quit();
$ maxima -q
(%i1) S: {-4, 6, 7, 32, 0};
(%o1)                         {- 4, 0, 6, 7, 32}
(%i2) adjoin(3, S);
(%o2)                        {- 4, 0, 3, 6, 7, 32}
(%i3) adjoin(7, S);
(%o3)                        {- 4, 0, 6, 7, 32}
(%i4) S: adjoin(3, S); /* Updating S */
(%o4)                       {- 4, 0, 3, 6, 7, 32}
(%i5) adjoin(7, S);
(%o5)                       {- 4, 0, 3, 6, 7, 32}
(%i6) disjoin(7, S);
(%o6)                        {- 4, 0, 3, 6, 32}
(%i7) disjoin(5, S);
(%o7)                       {- 4, 0, 3, 6, 7, 32}
(%i8) quit();
$ maxima -q
(%i1) S: {-4, 0, 3, 6, 7, 32};
(%o1)                        {- 4, 0, 3, 6, 7, 32}
(%i2) S1: subset(S, evenp);
(%o2)                           {- 4, 0, 6, 32}
(%i3) powerset(S1);
(%o3) {{}, {- 4}, {- 4, 0}, {- 4, 0, 6}, {- 4, 0, 6, 32}, {- 4, 0, 32}, {- 4, 6},
	{- 4, 6, 32}, {- 4, 32}, {0}, {0, 6}, {0, 6, 32}, {0, 32}, {6}, {6, 32},
	{32}}
(%i4) S2: {-35, -26, 0, 7, 32, 100};
(%o4)                     {- 35, - 26, 0, 7, 32, 100}
(%i5) symmdifference(S1, S2);
(%o5)                    {- 35, - 26, - 4, 6, 7, 100}
(%i6) symmdifference(S, S2);
(%o6)                    {- 35, - 26, - 4, 3, 6, 100}
(%i7) quit();

Advanced set operations

With Maxima, much more than this can be done with sets, just by the functionalities provided by it. So now, let’s journey through such interesting advance functionalities:

Cartesian Product:

Given n sets, the function cartesian_product() returns a set of lists formed by the Cartesian product of the n sets. The following demonstration explains what it means:

$ maxima -q
(%i1) cartesian_product({0, 1, 2}, {a, b, c});
(%o1) {[0, a], [0, b], [0, c], [1, a], [1, b], [1, c], [2, a], [2, b], [2, c]}
(%i2) cartesian_product({0, 1}, {a, b}, {X, Y});
(%o2) {[0, a, X], [0, a, Y], [0, b, X], [0, b, Y], [1, a, X], [1, a, Y], [1, b, X],
	[1, b, Y]}
(%i3) cartesian_product({0, 1}, {a, b, c});
(%o3)          {[0, a], [0, b], [0, c], [1, a], [1, b], [1, c]}
(%i4) quit();

Set Partitions:

Given a set S, it could be partitioned into various subsets, based on various mathematical principles. Maxima provides a host of functions for such partitioning. The basic one being set_partitions(). It returns a set of all possible partitions of the given set. With a number as the second argument, it gives only the partitions with that exact number of sets in each partition. Examples follow to make sense out of this:

$ maxima -q
(%i1) S: {a, b, c};
(%o1)                              {a, b, c}
(%i2) set_partitions(S);
(%o2) {{{a}, {b}, {c}}, {{a}, {b, c}}, {{a, b}, {c}}, {{a, b, c}}, {{a, c}, {b}}}
(%i3) set_partitions(S, 1);
(%o3)                            {{{a, b, c}}}
(%i4) set_partitions(S, 2);
(%o4)            {{{a}, {b, c}}, {{a, b}, {c}}, {{a, c}, {b}}}
(%i5) set_partitions(S, 3);
(%o5)                          {{{a}, {b}, {c}}}
(%i6) set_partitions(S, 4);
(%o6)                                 {}
(%i7) belln(3);
(%o7)                                  5
(%i8) cardinality(set_partitions(S)); /* Number of elements */
(%o8)                                  5
(%i9) belln(4);
(%o9)                                 15
(%i10) belln(5);
(%o10)                                 52
(%i11) belln(6);
(%o11)                                 203
(%i12) quit();

In the above examples, belln() – the nth Bell number is the number of partitions of a set with n members.

integer_partitions(n) is a specific function, which partitions a given positive integer n into set of positive integers, sum of which adds up to the original integer. num_partitions(n) returns the number of such partitions returned by integer_partitions(n). Examples follow:

$ maxima -q
(%i1) integer_partitions(1);
(%o1)                                {[1]}
(%i2) num_partitions(1);
(%o2)                                 1
(%i3) integer_partitions(2);
(%o3)                            {[1, 1], [2]}
(%i4) num_partitions(2);
(%o4)                                 2
(%i5) integer_partitions(3);
(%o5)                      {[1, 1, 1], [2, 1], [3]}
(%i6) num_partitions(3);
(%o6)                                 3
(%i7) integer_partitions(4);
(%o7)           {[1, 1, 1, 1], [2, 1, 1], [2, 2], [3, 1], [4]}
(%i8) num_partitions(4);
(%o8)                                 5
(%i9) integer_partitions(0);
(%o9)                                {[]}
(%i10) num_partitions(0);
(%o10)                                 1
(%i11) integer_partitions(5, 1);
(%o11)                                {[5]}
(%i12) integer_partitions(5, 2);
(%o12)                      {[3, 2], [4, 1], [5, 0]}
(%i13) integer_partitions(5, 3);
(%o13)       {[2, 2, 1], [3, 1, 1], [3, 2, 0], [4, 1, 0], [5, 0, 0]}
(%i14) integer_partitions(5, 4);
(%o14) {[2, 1, 1, 1], [2, 2, 1, 0], [3, 1, 1, 0], [3, 2, 0, 0], [4, 1, 0, 0],
	[5, 0, 0, 0]}
(%i15) integer_partitions(5, 5);
(%o15) {[1, 1, 1, 1, 1], [2, 1, 1, 1, 0], [2, 2, 1, 0, 0], [3, 1, 1, 0, 0],
	[3, 2, 0, 0, 0], [4, 1, 0, 0, 0], [5, 0, 0, 0, 0]}
(%i16) num_partitions(5);
(%o16)                                 7
(%i17) num_distinct_partitions(5);
(%o17)                                 3
(%i18) quit();

Note that like set_partitions(), integer_partitions() also takes an optional second argument, limiting the partitions to partitions of cardinality equal to that number. However, note that all smaller size partitions are made equal to the corresponding size by adding the required number of zeroes.

Also, num_distinct_partitions(n) returns number of distinct integer partitions of n, i.e. integer partitions of n with only distinct integers.

Another powerful partitioning function is the function equiv_classes(S, r), which returns a partition of S, elements of which satisfy the binary relation r. Here goes a few examples:

$ maxima -q
(%i1) equiv_classes({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, lambda([x, y],
	remainder(x - y, 2) = 0));
(%o1)               {{0, 2, 4, 6, 8, 10}, {1, 3, 5, 7, 9}}
(%i2) equiv_classes({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, lambda([x, y],
	remainder(x - y, 3) = 0));
(%o2)              {{0, 3, 6, 9}, {1, 4, 7, 10}, {2, 5, 8}}
(%i3) equiv_classes({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, lambda([x, y],
	remainder(x - y, 5) = 0));
(%o3)            {{0, 5, 10}, {1, 6}, {2, 7}, {3, 8}, {4, 9}}
(%i4) equiv_classes({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, lambda([x, y],
	remainder(x - y, 6) = 0));
(%o4)           {{0, 6}, {1, 7}, {2, 8}, {3, 9}, {4, 10}, {5}}
(%i5) equiv_classes({1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, lambda([x, y],
	remainder(x, y) = 0));
(%o5)             {{1, 2, 4, 8}, {3, 6}, {5, 10}, {7}, {9}}
(%i6) quit();

Notice the relation being defined using lamda() for the property of divisibility by 2, 3, 5, 6, and among the set elements themselves, respectively.

A closely related function partition_set(S, p) partitions S into 2 sets, one with elements satisfying the predicate p, and the other not satisfying the predicate p. Small demonstration follows:

$ maxima -q
(%i1) partition_set({-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 19, 26, 37, 100},
	primep);
(%o1) [{- 1, 0, 1, 4, 6, 8, 9, 10, 26, 100}, {2, 3, 5, 7, 11, 19, 37}]
(%i2) quit();

Miscellaneous:

And finally, lets look at some general but mathematically interesting operations:

  • divisors(n) – returns the set of positive divisors of n
  • permutations(S) – returns the set of all permutations of the elements of S
  • random_permutation(S) – returns one of the elements of permutations(S), randomly
  • extremal_subset(S, f, max | min) – returns the subset of S, for which the value of the function f is maximum or minimum

An all-together demonstration follows:

$ maxima -q
(%i1) divisors(9);
(%o1)                             {1, 3, 9}
(%i2) divisors(28);
(%o2)                       {1, 2, 4, 7, 14, 28}
(%i3) permutations({a, b, c});
(%o3) {[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a, b], [c, b, a]}
(%i4) random_permutation({a, b, c});
(%o4)                             [c, b, a]
(%i5) random_permutation({a, b, c});
(%o5)                              [c, a, b]
(%i6) random_permutation({a, b, c});
(%o6)                              [b, c, a]
(%i7) extremal_subset({-5, -3, -1, 0, 1, 2, 3, 4, 5}, lambda([x], x*x), max);
(%o7)                            {- 5, 5}
(%i8) extremal_subset({-5, -3, -1, 0, 1, 2, 3, 4, 5}, lambda([x], x*x), min);
(%o8)                               {0}
(%i9) quit();

Twentieth Article >>

   Send article as PDF