Monthly Archives: December 2014

The Semester Project – Part VI: File System on Block Device

This twenty-third article, which is part of the series on Linux device drivers, enhances the previously written bare bone file system module, to connect with a real hardware partition.

<< Twenty-second Article

Since the last bare bone file system, the first thing which Pugs figured out was how to read from the underlying block device. Following is a typical way of doing it:

struct buffer_head *bh;

bh = sb_bread(sb, block); /* sb is the struct super_block pointer */
// bh->b_data contains the data
// Once done, bh should be released using:
brelse(bh);

To do the above and various other real SFS (Simula File System) operations, Pugs’ felt a need to have his own handle to be a key parameter, which he added as follows (in previous real_sfs_ds.h):

typedef struct sfs_info
{
	struct super_block *vfs_sb; /* Super block structure from VFS for this fs */
	sfs_super_block_t sb; /* Our fs super block */
	byte1_t *used_blocks; /* Used blocks tracker */
} sfs_info_t;

The main idea behind this was to put all required static global variables in a single structure, and point that by the private data pointer of the file system, which is s_fs_info pointer in the struct super_block structure. With that, the key changes in the fill_super_block() (in previous real_sfs_bb.c file) becomes:

  • Allocate the structure for the handle, using kzalloc()
  • Initialize the structure for the handle (through init_browsing())
  • Read the physical super block, verify and translate info from it into the VFS super block (through init_browsing())
  • Point it by s_fs_info (through init_browsing())
  • Update the VFS super block, accordingly

Accordingly, the error handling code would need to do the shut_browsing(info) and kfree(info). And, that would additionally also need to go along with the function corresponding to the kill_sb function pointer, defined in the previous real_sfs_bb.c by kill_block_super, called during umount.

Here’s the various code pieces:

#include <linux/slab.h> /* For kzalloc, ... */
...
static int sfs_fill_super(struct super_block *sb, void *data, int silent)
{
	sfs_info_t *info;

	if (!(info = (sfs_info_t *)(kzalloc(sizeof(sfs_info_t), GFP_KERNEL))))
		return -ENOMEM;
	info->vfs_sb = sb;
	if (init_browsing(info) < 0)
	{
		kfree(info);
		return -EIO;
	}
	/* Updating the VFS super_block */
	sb->s_magic = info->sb.type;
	sb->s_blocksize = info->sb.block_size;
	sb->s_blocksize_bits = get_bit_pos(info->sb.block_size);

	...
}

static void sfs_kill_sb(struct super_block *sb)
{
	sfs_info_t *info = (sfs_info_t *)(sb->s_fs_info);

	kill_block_super(sb);
	if (info)
	{
		shut_browsing(info);
		kfree(info);
	}
}

kzalloc() in contrast to kmalloc(), also zeroes out the allocated location. get_bit_pos() is a simple Pugs’ way to compute logarithm base 2, as follows:

static int get_bit_pos(unsigned int val)
{
	int i;

	for (i = 0; val; i++)
	{
		val >>= 1;
	}
	return (i - 1);
}

And init_browsing(), shut_browsing() are basically the transformations of the earlier user-space functions of browse_real_sfs.c into kernel-space code real_sfs_ops.c, prototyped in real_sfs_ops.h. This basically involves the following transformations:

  • int sfs_handle” into “sfs_info_t *info
  • lseek() & read() into the read from the block device using sb_bread()
  • calloc() into vmalloc() & then appropriate initialization by zeros.
  • free() into vfree()

Here’s the transformed init_browsing() and shut_browsing() in real_sfs_ops.c:

#include <linux/fs.h> /* For struct super_block */
#include <linux/errno.h> /* For error codes */
#include <linux/vmalloc.h> /* For vmalloc, ... */

#include "real_sfs_ds.h"
#include "real_sfs_ops.h"

int init_browsing(sfs_info_t *info)
{
	byte1_t *used_blocks;
	int i, j;
	sfs_file_entry_t fe;
	int retval;

	if ((retval = read_sb_from_real_sfs(info, &info->sb)) < 0)
	{
		return retval;
	}
	if (info->sb.type != SIMULA_FS_TYPE)
	{
		printk(KERN_ERR "Invalid SFS detected. Giving up.\n");
		return -EINVAL;
	}

	/* Mark used blocks */
	used_blocks = (byte1_t *)(vmalloc(info->sb.partition_size));
	if (!used_blocks)
	{
		return -ENOMEM;
	}
	for (i = 0; i < info->sb.data_block_start; i++)
	{
		used_blocks[i] = 1;
	}
	for (; i < info->sb.partition_size; i++)
	{
		used_blocks[i] = 0;
	}

	for (i = 0; i < info->sb.entry_count; i++)
	{
		if ((retval = read_from_real_sfs(info,
					info->sb.entry_table_block_start,
					i * sizeof(sfs_file_entry_t),
					&fe, sizeof(sfs_file_entry_t))) < 0)
		{
			vfree(used_blocks);
			return retval;
		}
		if (!fe.name[0]) continue;
		for (j = 0; j < SIMULA_FS_DATA_BLOCK_CNT; j++)
		{
			if (fe.blocks[j] == 0) break;
			used_blocks[fe.blocks[j]] = 1;
		}
	}

	info->used_blocks = used_blocks;
	info->vfs_sb->s_fs_info = info;
	return 0;
}
void shut_browsing(sfs_info_t *info)
{
	if (info->used_blocks)
		vfree(info->used_blocks);
}

Similarly, all other functions in browse_real_sfs.c would also have to be transformed, one by one. Also, note the read from the underlying block device is being captured by the two functions, namely read_sb_from_real_sfs() and read_from_real_sfs(), which are coded as follows:

#include <linux/buffer_head.h> /* struct buffer_head, sb_bread, ... */
#include <linux/string.h> /* For memcpy */

#include "real_sfs_ds.h"

static int read_sb_from_real_sfs(sfs_info_t *info, sfs_super_block_t *sb)
{
	struct buffer_head *bh;

	if (!(bh = sb_bread(info->vfs_sb, 0 /* Super block is the 0th block */)))
	{
		return -EIO;
	}
	memcpy(sb, bh->b_data, SIMULA_FS_BLOCK_SIZE);
	brelse(bh);
	return 0;
}
static int read_from_real_sfs(sfs_info_t *info, byte4_t block,
				byte4_t offset, void *buf, byte4_t len)
{
	byte4_t block_size = info->sb.block_size;
	byte4_t bd_block_size = info->vfs_sb->s_bdev->bd_block_size;
	byte4_t abs;
	struct buffer_head *bh;

	/*
	 * Translating the real SFS block numbering to underlying block device
	 * block numbering, for sb_bread()
	 */
	abs = block * block_size + offset;
	block = abs / bd_block_size;
	offset = abs % bd_block_size;
	if (offset + len > bd_block_size) // Should never happen
	{
		return -EINVAL;
	}
	if (!(bh = sb_bread(info->vfs_sb, block)))
	{
		return -EIO;
	}
	memcpy(buf, bh->b_data + offset, len);
	brelse(bh);
	return 0;
}

All the above code pieces put in together as the real_sfs_minimal.c (based on the file real_sfs_bb.c created earlier), real_sfs_ops.c, real_sfs_ds.h (based on the same file created earlier), real_sfs_ops.h, and a supporting Makefile, along with the previously created format_real_sfs.c application are available from rsfs_on_block_device_code.tbz2.

Real SFS on block device

Once compiled using make, getting the real_sfs_first.ko driver, Pugs didn’t expect it to be way different from the previous real_sfs_bb.ko driver, but at least now it should be reading and verifying the underlying partition. And for that he first tried mounting the usual partition of a pen drive to get an “Invalid SFS detected” message in dmesg output; and then after formatting it. Note the same error of “Not a directory”, etc as in previous article, still existing – as anyways it is still very similar to the previous bare bone driver – the core functionalities yet to be implemented – just that it is now on a real block device partition. Figure 39 shows the exact commands for all these steps.

Figure 39: Connecting the SFS module with the pen drive partition

Figure 39: Connecting the SFS module with the pen drive partition

Note: “./format_real_sfs” and “mount” commands may take lot of time (may be in minutes), depending on the partition size. So, preferably use a partition, say less than 1MB.

With this important step of getting the file system module interacting with the underlying block device, the last step for Pugs would be to do the other transformations from browse_real_sfs.c and accordingly use them in the SFS module.

Twenty-fourth Article >>

www.pdf24.org    Send article as PDF   

Visualizing Graph Theory

This twenty-third article of the mathematical journey through open source, introduces graph theory with visuals using the graphs package of Maxima.

<< Twenty-second Article

Graphs here refer to the structures formed using some points (or vertices), and some lines (or edges) connecting them. A simple example would be a graph with two vertices, say ‘0’ & ‘1’, and an edge between ‘0’ and ‘1’. If all the edges of a graph have a sense of direction from one vertex to another, typically represented by an arrow at their end(s), we call that a directed graph with directed edges. In such a case, we consider the edges to be not between two vertices but from one vertex to another vertex. Directed edges are also referred to as arcs. In the above example, we could have two directed arcs, one from ‘0’ to ‘1’, and another from ‘1’ to ‘0’. Figures 24 & 25 show an undirected and a directed graph, respectively.

Figure 24: Simple undirected graph

Figure 24: Simple undirected graph

Figure 25: Simple directed graph

Figure 25: Simple directed graph

Graph creation & visualization

Now, how did we get those figures? Using the graphs package of Maxima, which is loaded by invoking load(graphs) at the Maxima prompt. In the package, vertices are represented by whole numbers 0, 1, … and an edge is represented as a list of its two vertices. Using these notations, we can create graphs using the create_graph(<vertex_list>, <edge_list>[, directed]) function. And, then draw_graph(<graph>[, <option1>, <option2>, …]) would draw the graph pictorially. Code snippet below shows the same in action:

$ maxima -q
(%i1) load(graphs)$
...
0 errors, 0 warnings
(%i2) g: create_graph([0, 1], [[0, 1]])$
(%i3) dg: create_graph([0, 1], [[0, 1]], directed=true)$
(%i4) draw_graph(g, show_id=true, vertex_size=5, vertex_color=yellow)$
(%i5) draw_graph(dg, show_id=true, vertex_size=5, vertex_color=yellow)$

The “show_id=true” option draws the vertex numbers, and vertex_size and vertex_color draws the vertices with the corresponding size and colour.

Note that a graph without any duplicate edges and without any loops is called a simple graph. And, an edge from a vertex U to V is not duplicate of an edge from vertex V to U in a directed graph but is duplicate in an undirected graph. Maxima’s package supports only simple graphs, i.e. graphs without duplicate edges and loops.

A simple graph can also be equivalently represented by adjacency of vertices, meaning by lists of adjacent vertices for every vertex. print_graph(<graph>) exactly displays those lists. The following code demonstration, in continuation from the previous code, demonstrates that:

(%i6) print_graph(g)$

Graph on 2 vertices with 1 edges.
Adjacencies:
  1 :  0
  0 :  1
(%i7) print_graph(dg)$

Digraph on 2 vertices with 1 arcs.
Adjacencies:
  1 :
  0 :  1
(%i8) quit();

create_graph(<num_of_vertices>, <edge_list>[, directed]) is another way of creating a graph using create_graph(). Here, the vertices are created as 0, 1, …, <num_of_vertices> – 1. So, both the above graphs could equivalently be created as follows:

$ maxima -q
(%i1) load(graphs)$
...
0 errors, 0 warnings
(%i2) g: create_graph(2, [[0, 1]]);
(%o2)                     GRAPH(2 vertices, 1 edges)
(%i3) dg: create_graph(2, [[0, 1]], directed=true);
(%o3)                     DIGRAPH(2 vertices, 1 arcs)
(%i4) quit();

make_graph(<vertices>, <predicate>[, directed]) is another interesting way of creating a graph, based on vertex connectivity conditions specified by the <predicate> function. <vertices> could be an integer or a set/list of vertices. If it is a positive integer, then the vertices would be 1, 2, …, <vertices>. In any case, <predicate> should be a function taking two arguments of the vertex type and returning true or false. make_graph() creates a graph with the vertices specified as above, and with the edges between the vertices for which the <predicate> function returns true.

A trivial case would be, if the <predicate> always returns true, then it would create a complete graph, i.e. a simple graph where all vertices are connected to each other. Here are a couple of demonstrations of make_graph():

$ maxima -q
(%i1) load(graphs)$
...
0 errors, 0 warnings
(%i2) f(i, j) := true$
(%i3) g: make_graph(6, f);
(%o3)                   GRAPH(6 vertices, 15 edges)
(%i4) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i5) f(i, j) := is(mod(i, j)=0)$
(%i6) g: make_graph(10, f, directed = true);
(%o6)                  DIGRAPH(10 vertices, 17 arcs)
(%i7) draw_graph(g, show_id=true, vertex_color=yellow, vertex_size=4)$
(%i8) quit();

Figures 26 shows the output graphs from the above code.

Figure 26: More simple graphs

Figure 26: More simple graphs

Graph varieties

One aware of graphs, would have known or at least heard of a variety of them. Here’s a list of some of them, available in Maxima’s graphs package (through functions):

  • Empty graph (empty_graph(n)) – Graph with a given n vertices but no edges
  • Complete graph (complete_graph(n)) – Simple graph with all possible edges for a given n vertices
  • Complete bipartite graph (complete_bipartite_graph(m, n)) – Simple graph with two set of vertices, having all possible edges between the vertices from the two sets, but with no edge between the vertices of the same set.
  • Cube graph (cube_graph(n)) – Graph representing an n-dimensional cube
  • Dodecahedron graph (dodecahedron_graph()) – Graph forming a 3-D polyhedron with 12 pentagonal faces
  • Cuboctahedron graph (cuboctahedron_graph()) – Graph forming a 3-D polyhedron with 8 triangular faces and 12 square faces
  • Icosahedron graph (icosahedron_graph()) – Graph forming a 3-D polyhedron with 20 triangular faces
  • Icosidodecahedron graph (icosidodecahedron_graph()) – Graph forming a 3-D uniform star polyhedron with 12 star faces and 20 triangular faces

And here follows a demonstration of the above, along with the visuals (left to right, top to bottom) in Figure 27:

$ maxima -q
(%i1) load(graphs)$
...
0 errors, 0 warnings
(%i2) g: empty_graph(5);
(%o2)                     GRAPH(5 vertices, 0 edges)
(%i3) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i4) g: complete_graph(5);
(%o4)                     GRAPH(5 vertices, 10 edges)
(%i5) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i6) g: complete_bipartite_graph(5, 3);
(%o6)                     GRAPH(8 vertices, 15 edges)
(%i7) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i8) g: cube_graph(3);
(%o8)                    GRAPH(8 vertices, 12 edges)
(%i9) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i10) g: cube_graph(4);
(%o10)                   GRAPH(16 vertices, 32 edges)
(%i11) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i12) g: dodecahedron_graph();
(%o12)                   GRAPH(20 vertices, 30 edges)
(%i13) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i14) g: cuboctahedron_graph();
(%o14)                   GRAPH(12 vertices, 24 edges)
(%i15) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i16) g: icosahedron_graph();
(%o16)                   GRAPH(12 vertices, 30 edges)
(%i17) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i18) g: icosidodecahedron_graph();
(%o18)                   GRAPH(30 vertices, 60 edges)
(%i19) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i20) quit();
Figure 27: Graph varieties

Figure 27: Graph varieties

Graph beauties

Graphs are really beautiful to visualize. Some of the many beautiful graphs, available in Maxima’s graphs package (through functions), are listed below:

  • Circulant graph (circulant_graph(n, [x, y, …])) – Graph with vertices 0, …, n-1, where every vertex is adjacent to its xth, yth, … vertices. Visually, it has a cyclic group of symmetries./li>
  • Flower graph (flower_snark(n)) – Graph like a flower with n petals and 4*n vertices
  • Wheel graph (wheel_graph(n)) – Graph like a wheel with n vertices
  • Clebsch graph (clebsch_graph()) – An another symmetrical graph beauty, named by J J Seidel
  • Frucht graph (frucht_graph()) – A graph with 12 vertices, 18 edges, and no nontrivial symmetries, such that every vertex have 3 neighbours. It is named after Robert Frucht
  • Grötzsch graph (grotzch_graph()) – A triangle-free graph with 11 vertices and 20 edges, named after Herbert Grötzsch
  • Heawood graph (heawood_graph()) – A symmetrical graph with 14 vertices and 21 edges, named after Percy John Heawood
  • Petersen graph (petersen_graph()) – A symmetrical graph with 10 vertices and 15 edges, named after Julius Petersen
  • Tutte graph (tutte_graph()) – A graph with 46 vertices and 69 edges, such that every vertex have 3 neighbours. It is named after W T Tutte

And here follows a demonstration of some of the above, along with the visuals (left to right, top to bottom) in Figure 28:

$ maxima -q
(%i1) load(graphs)$
...
0 errors, 0 warnings
(%i2) g: circulant_graph(10, [1, 3]);
(%o2)                   GRAPH(10 vertices, 20 edges)
(%i3) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i4) g: circulant_graph(10, [1, 3, 4, 6]);
(%o4)                   GRAPH(10 vertices, 40 edges)
(%i5) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i6) g: flower_snark(3);
(%o6)                   GRAPH(12 vertices, 18 edges)
(%i7) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i8) g: flower_snark(5);
(%o8)                   GRAPH(20 vertices, 30 edges)
(%i9) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i10) g: flower_snark(8);
(%o10)                   GRAPH(32 vertices, 48 edges)
(%i11) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i12) g: flower_snark(10);
(%o12)                   GRAPH(40 vertices, 60 edges)
(%i13) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i14) g: wheel_graph(3);
(%o14)                    GRAPH(4 vertices, 6 edges)
(%i15) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i16) g: wheel_graph(4);
(%o16)                    GRAPH(5 vertices, 8 edges)
(%i17) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i18) g: wheel_graph(5);
(%o18)                    GRAPH(6 vertices, 10 edges)
(%i19) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i20) g: wheel_graph(10);
(%o20)                   GRAPH(11 vertices, 20 edges)
(%i21) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i22) g: wheel_graph(100);
(%o22)                  GRAPH(101 vertices, 200 edges)
(%i23) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i24) g: clebsch_graph();
(%o24)                   GRAPH(16 vertices, 40 edges)
(%i25) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i26) g: grotzch_graph();
(%o26)                   GRAPH(11 vertices, 20 edges)
(%i27) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i28) g: petersen_graph();
(%o28)                   GRAPH(10 vertices, 15 edges)
(%i29) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i30) g: tutte_graph();
(%o30)                   GRAPH(46 vertices, 69 edges)
(%i31) draw_graph(g, show_id=true, vertex_color=yellow)$
(%i32) quit();
Figure 28: Graph beauties

Figure 28: Graph beauties

What next?

With all these visualizations, you may be wondering, what to do with these apart from just staring at them. Visualizations were just to motivate you, visually. In fact, every graph has a particular set of properties, which distinguishes it from the other. And, there is a lot of beautiful mathematics involved with these properties. If you are motivated enough, watch out for playing around with these graphs and their properties.

Twenty-fourth Article >>

www.pdf24.org    Send article as PDF