Monthly Archives: November 2014

The Semester Project – Part V: File System Module Template

This twenty-second article, which is part of the series on Linux device drivers, lays out a bare bone file system module.

<< Twenty-first Article

With the formatting of the pen drive, the file system is all set in the hardware space. Now, it is the turn to decode that using a corresponding file system module in the kernel space, and accordingly provide the user space file system interface, for it to be browsed like any other file systems.

The 5 sets of System Calls

Unlike character or block drivers, the file system drivers involve not just one structure of function pointers, but instead 5 structures of function pointers, for the various interfaces, provided by a file system. These are:

  • struct file_system_type – contains functions to operate on the super block
  • struct super_operations – contains functions to operate on the inodes
  • struct inode_operations – contains functions to operate on the directory entries
  • struct file_operations – contains functions to operate on the file data (through page cache)
  • struct address_space_operations – contains page cache operations for the file data

With these, there were many new terms for Pugs. He referred the following glossary to understand the various terms used above and later in the file system module development:

  • Page cache or Buffer cache: Pool of RAM buffers, each of page size (typically 4096 bytes). These buffers are used as the cache for the file data read from the underlying hardware, thus increasing the performance of file operations
  • Inode: Structure containing the meta data / information of a file, like permissions, owner, etc. Though file name is a meta data of a file, for better space utilization, in typical Linux file systems, it is not kept in inode, instead in something called directory entries. Collection of inodes, is called an inode table
  • Directory entry: Structure containing the name and inode number of a file or directory. In typical Linux based file systems, a collection of directory entries for the immediate files and directories of say directory D, is stored in the data blocks of the directory D
  • Super block: Structure containing the information about the various data structures of the file systems, like the inode tables, … Basically the meta meta data, i.e. meta data for the meta data
  • Virtual File System (VFS): Conceptual file system layer interfacing the kernel space to user space in an abstract manner, showing “everything” as a file, and translating their operations from user to the appropriate entity in the kernel space

Each one of the above five structures contains a list of function pointers, which needs to be populated depending on what all features are there or to be supported in the file system (module). For example, struct file_system_type may contain system calls for mounting and unmounting a file system, basically operating on its super block; struct super_operations may contain inode read/write system calls; struct inode_operations may contain function to lookup directory entries; struct file_operations may generically operate on the page cached file data, which may in turn invoke page cache operations, defined in the struct address_space_operations. For these various operations, most of these functions will then interface with the corresponding underlying block device driver to ultimately operate with the formatted file system in the hardware space.

To start with Pugs laid out the complete framework of his real SFS module, but with minimal functionality, good enough to compile, load, and not crash the kernel. He populated only the first of these five structures – the struct file_system_type; and left all the others empty. Here’s the exact code of the structure definitions:

#include <linux/fs.h> /* For system calls, structures, ... */

static struct file_system_type sfs;
static struct super_operations sfs_sops;
static struct inode_operations sfs_iops;
static struct file_operations sfs_fops;
static struct address_space_operations sfs_aops;
#include <linux/version.h> /* For LINUX_VERSION_CODE & KERNEL_VERSION */

static struct file_system_type sfs =
	name: "sfs", /* Name of our file system */
	get_sb:  sfs_get_sb,
	mount:  sfs_mount,
	kill_sb: kill_block_super,

Note that before Linux kernel version 2.6.38, the mount function pointer was referred as get_sb, and also, it used to have slightly different parameters. And hence, the above #if for it to be compatible at least across 2.6.3x and possibly with 3.x kernel versions – no guarantee for others. Accordingly, the corresponding functions sfs_get_sb() and sfs_mount(), are also #if’d, as follows:

#include <linux/kernel.h> /* For printk, ... */

static int sfs_get_sb(struct file_system_type *fs_type, int flags,
			const char *devname, void *data, struct vfsmount *vm)
	printk(KERN_INFO "sfs: devname = %s\n", devname);

	/* sfs_fill_super this will be called to fill the super block */
	return get_sb_bdev(fs_type, flags, devname, data, &sfs_fill_super, vm);
static struct dentry *sfs_mount(struct file_system_type *fs_type,
					int flags, const char *devname, void *data)
	printk(KERN_INFO "sfs: devname = %s\n", devname);

	/* sfs_fill_super this will be called to fill the super block */
	return mount_bdev(fs_type, flags, devname, data, &sfs_fill_super);

The only difference in the above 2 functions is that in the later, the VFS mount point related structure has been removed. The printk() in there would display the underlying partition’s device file which the user is going to mount, basically the pen drive’s SFS formatted partition. get_sb_bdev() and mount_bdev() are generic block device mount functions for the respective kernel versions, defined in fs/super.c and prototyped in <linux/fs.h>. Pugs also used them, as most other file system writers do. Are you wondering: Does all file system mount a block device, the same way? Most of it yes, except the part where the mount operation needs to fill in the VFS’ super block structure (struct super_block), as per the super block of the underlying file system – obviously that most probably would be different. But then how does it do that? Observe carefully, in the above functions, apart from passing all the parameters as is, there is an additional parameter sfs_fill_super, and that is Pugs’ custom function to fill the VFS’ super block, as per the SFS file system.

Unlike the mount function pointer, the unmount function pointer has been same (kill_sb) for quite some kernel versions; and in unmounting, there is not even the minimal distinction required across different file systems. So, the generic block device unmount function kill_block_super() has been used directly as the function pointer.

In sfs_fill_super(), Pugs is ideally supposed to read the super block from the underlying hardware-space SFS, and then accordingly translate and fill that into VFS’ super block to enable VFS to provide the user space file system interface. But he is yet to figure that out, as how to read from the underlying block device, in the kernel space. Information of which block device to use, is already embedded into the super_block structure itself, obtained from the user issuing the mount command. But as Pugs decided to get the bare bone real SFS up, first, he went ahead writing this sfs_super_fill() function also as a hard-coded fill function. And with that itself, he registered the Simula file system with the VFS. As any other Linux driver, here’s the file system driver’s constructor and destructor for that:

#include <linux/module.h> /* For module related macros, ... */

static int __init sfs_init(void)
	int err;

	err = register_filesystem(&sfs);
	return err;

static void __exit sfs_exit(void)


Both register_filesystem() and unregister_filesystem() takes pointer to the the struct file_system_type sfs (filled above), as their parameter, to respectively register and unregister the file system described by it.

Hard-coded SFS super block and root inode

And yes, here’s the hard-coded sfs_fill_super() function:

#include "real_sfs_ds.h" /* For SFS related defines, data structures, ... */

static int sfs_fill_super(struct super_block *sb, void *data, int silent)
	printk(KERN_INFO "sfs: sfs_fill_super\n");

	sb->s_blocksize = SIMULA_FS_BLOCK_SIZE;
	sb->s_blocksize_bits = SIMULA_FS_BLOCK_SIZE_BITS;
	sb->s_magic = SIMULA_FS_TYPE;
	sb->s_type = &sfs; // file_system_type
	sb->s_op = &sfs_sops; // super block operations

	sfs_root_inode = iget_locked(sb, 1); // obtain an inode from VFS
	if (!sfs_root_inode)
		return -EACCES;
	if (sfs_root_inode->i_state & I_NEW) // allocated fresh now
		printk(KERN_INFO "sfs: Got new root inode, let's fill in\n");
		sfs_root_inode->i_op = &sfs_iops; // inode operations
		sfs_root_inode->i_mode = S_IFDIR | S_IRWXU |
		sfs_root_inode->i_fop = &sfs_fops; // file operations
		sfs_root_inode->i_mapping->a_ops = &sfs_aops; // address operations
		printk(KERN_INFO "sfs: Got root inode from inode cache\n");

	sb->s_root = d_alloc_root(sfs_root_inode);
	sb->s_root = d_make_root(sfs_root_inode);
	if (!sb->s_root)
		return -ENOMEM;

	return 0;

As mentioned earlier, this function is basically supposed to read the underlying SFS super block, and accordingly translate and fill the struct super_block, pointed to by its first parameter sb. So, understanding it is same as understanding the minimal fields of the struct super_block, which are getting filled up. The first three are the block size, its logarithm base 2, and the type/magic code of the Simula file system. As Pugs codes further, we shall see that once he gets the super block from the hardware space, he would instead get these values from that super block, and more importantly verify them, to ensure that the correct partition is being mounted.

After that, the various structure pointers are pointed to their corresponding structure of the function pointers. Last but not least, the root inode’s pointer s_root is pointed to the struct inode structure, obtained from VFS’ inode cache, based on the inode number of root – right now, which has been hard coded to 1 – it may possibly change. If the inode structure is obtained fresh, i.e. for the first time, it is then filled as per the underlying SFS’ root inode’s content. Also, the mode field is being hard-coded to “drwxr-xr-x“. Apart from that, the usual structure pointers are being initialized by the corresponding structure addresses. And finally, the root’s inode is being attached to the super block using d_alloc_root() or d_make_root(), as per the kernel version.

All the above code pieces put in together as the bare bone real_sfs_bb.c, along with the real_sfs_ds.h (based on the same file created earlier), and a supporting Makefile are available from rsfsbb_code.tbz2.

Bare bone SFS module in action

Once compiled using make, getting the real_sfs_bb.ko driver, Pugs did his usual unusual experiments, shown as in Figure 38.

Figure 38: Bare-bone real SFS experiments

Figure 38: Bare-bone real SFS experiments

Pugs’ experiments (Explanation of Figure 38):

  • Checked the kernel window /proc/filesystems for the kernel supported file systems
  • Loaded the real_sfs_bb.ko driver
  • Re-checked the kernel window /proc/filesystems for the kernel supported file systems. Now, it shows sfs listed at the end
  • Did a mount of his pen drive partition /dev/sdb1 onto /mnt using the sfs file system. Checked the dmesg logs on the adjacent window. (Keep in mind, that right now, the sfs_fill_super() is not really reading the partition, and hence not doing any checks. So, it really doesn’t matter as to how the /dev/sdb1 is formatted.) But yes, the mount output shows that it is mounted using the sfs file system

Oops!!! But df output shows “Function not implemented”, cd gives “Not a directory”. Aha!! Pugs haven’t implemented any other functions in any of the other four function pointer structures, yet. So, that’s expected.

Note: The above experiments are using “sudo”. Instead one may get into root shell and do the same without a “sudo”.

Okay, so no kernel crashes, and a bare bone file system in action – Yippee. Ya! Ya! Pugs knows that df, cd, … are not yet functional. For that, he needs to start adding the various system calls in the other (four) function pointer structures to be able to do cool-cool browsing, the same way as is done with all other file systems, using the various shell commands. And yes, Pugs is already onto his task – after all he needs to have a geeky demo for his final semester project.

Twenty-third Article >>

   Send article as PDF   

Manage your Finances with Maxima

This twenty-second article of the mathematical journey through open source, show cases managing our usual financial computations using the financial package of Maxima.

<< Twenty-first Article

In today’s credit-oriented world, loan, EMIs, the principal, interest rates, savings, etc are the common lingo. How well do we really understand these, or for that matter are able to compute the actual finances related to such things? Or, do we just accept what the other party has to provide us. One may say, either get into the gory details to understand and verify, or forget about understanding and just accept it if the offering suits you – you cannot not understand and also verify at the same time. However, with the finance package of Maxima, you can actually verify without getting much into the computational details. This article is going to exactly walk you through that.

Basic operations

To be able to use the finance package of Maxima, the first thing to do, after getting the Maxima prompt is to load the finance package, using load(). And, then go ahead to do the various computations. days360() is the simplest function to give the number of days between two dates, assuming 360 days per year, 30 days per month – one of the common interest calculation norm.

$ maxima -q
(%i1) load(finance);
(%o1)     /usr/share/maxima/5.24.0/share/contrib/finance/finance.mac
(%i2) days360(2014, 1, 1, 2014, 10, 1);
(%o2)                                 270
(%i3) days360(2014, 1, 1, 2014, 12, 31);
(%o3)                                 360
(%i4) days360(2014, 1, 1, 2014, 3, 1);
(%o4)                                 60
(%i5) days360(2014, 1, 1, 2015, 1, 1);
(%o5)                                 360
(%i6) quit();

Note that days360() takes from and to dates, each as a triplet of year, month, date.

One common computation, we often deal with, is the final amount we would get after applying a particular rate of compound interest on a particular principal amount – just use fv(<rate>, <principal>, <period>) for computing the future value of the <principal>, at the compound interest rate of <rate>, after <period> periods of the rate. As an example, what would be the future value of investing ₹10,000 for 10 years at the compound interest rate of 15% per year – just call fv(0.15, 10000, 10);

$ maxima -q
(%i1) load(finance)$ /* $ to suppress its output */
(%i2) fv(0.15, 10000, 10);
(%o2)                          40455.57735707907

If you are interested in, how exactly did it calculate, or what is the formula, that is where Maxima is fun to play with symbols. Just use some symbols, instead of actual numbers:

(%i3) string(fv(r, p, n));
(%o3)                              p*(r+1)^n
(%i4) quit();

And, there you go. p*(r+1)^n is the future value for investing p amount for n periods at the compounded interest rate of r per period.

How about doing an inverse computation? Suppose, I want to get ₹10,00,000 after 5 years from my investment today at the interest rate of 10.75%. Now for that, how much should I invest today? Don’t scratch your head, just call pv(<rate>, <future_val>, <period>);

(%i1) load(finance)$
(%i2) pv(0.1075, 1000000, 5);
(%o2)                          600179.7323625274
(%i3) fv(0.1075, 600180, 5);
(%o3)                          1000000.445928875
(%i4) quit();

That requires an investment of ₹6,00,180. Yes, so if you invest that amount, the future value would be ₹10,00,000 – that’s the check done above using fv().

Loans and EMIs

Fundamental thought behind today’s culture of buying a house, a car, or even smaller items is “let’s buy it on loan and pay it off in EMIs (equated monthly installments)”. These terms would be familiar to most of you, so no need to explain them. But, how do you compute these? One would say, there are some complicated formulas to do so. Yes, you are right. But, you don’t need to worry about any of them. Just tell Maxima to give you the complete schedule for your loan, at a given rate of interest, for a given period of time, using amortization(). The first example below provides the schedule for a home loan of ₹20 lakhs at an interest rate of 9.25% per annum (p.a.) for 5 years. The various columns in the output schedule provide the following information:

  • n: installment payment time – year for our example
  • Balance: principal + interest left over to be paid out, after the current installment is paid out
  • Interest: interest part being paid out in the current installment
  • Amortization: principal part being paid out in the current installment
  • Payment: current installment to be paid out, i.e. the EYI (equated yearly installment)

What is this EYI? We were supposed to talk only about EMI, right? Okay, in that case, we need to convert the rate of interest and the period, both in terms of months. So, we need to divide the per annum rate of interest by 12 to get it per month, and multiply the number of years by 12 to get that in number of months. That is exactly what the second example below shows. Note the 60 EMIs to be paid out over the period of 5 years.

$ maxima -q
(%i1) load(finance)$
(%i2) amortization(0.0925, 2000000, 5)$
           "n"      "Balance"    "Interest"  "Amortization"  "Payment"      
          0.000   2000000.000         0.000         0.000         0.000  
          1.000   1667475.420    185000.000    332524.580    517524.580  
          2.000   1304192.317    154241.476    363283.103    517524.580  
          3.000    907305.527    120637.789    396886.790    517524.580  
          4.000    473706.709     83925.761    433598.818    517524.580  
          5.000         0.000     43817.871    473706.709    517524.580  

(%i3) amortization(0.0925/12, 2000000, 5*12)$
           "n"      "Balance"    "Interest"  "Amortization"  "Payment"      
          0.000   2000000.000         0.000         0.000         0.000  
          1.000   1973656.870     15416.667     26343.130     41759.797  
          2.000   1947110.679     15213.605     26546.192     41759.797  
          3.000   1920359.860     15008.978     26750.818     41759.797  
          4.000   1893402.837     14802.774     26957.023     41759.797  
          5.000   1866238.021     14594.980     27164.816     41759.797  
          6.000   1838863.809     14385.585     27374.212     41759.797  
          7.000   1811278.588     14174.575     27585.221     41759.797  
          8.000   1783480.730     13961.939     27797.857     41759.797  
          9.000   1755468.598     13747.664     28012.133     41759.797  
         10.000   1727240.538     13531.737     28228.059     41759.797  
         11.000   1698794.887     13314.146     28445.651     41759.797  
         12.000   1670129.968     13094.877     28664.919     41759.797  
         13.000   1641244.090     12873.919     28885.878     41759.797  
         14.000   1612135.550     12651.257     29108.540     41759.797  
         15.000   1582802.632     12426.878     29332.918     41759.797  
         16.000   1553243.605     12200.770     29559.026     41759.797  
         17.000   1523456.728     11972.919     29786.877     41759.797  
         18.000   1493440.244     11743.312     30016.484     41759.797  
         19.000   1463192.382     11511.935     30247.861     41759.797  
         20.000   1432711.360     11278.775     30481.022     41759.797  
         21.000   1401995.381     11043.817     30715.980     41759.797  
         22.000   1371042.632     10807.048     30952.749     41759.797  
         23.000   1339851.289     10568.454     31191.343     41759.797  
         24.000   1308419.513     10328.020     31431.776     41759.797  
         25.000   1276745.450     10085.734     31674.063     41759.797  
         26.000   1244827.233      9841.580     31918.217     41759.797  
         27.000   1212662.979      9595.543     32164.253     41759.797  
         28.000   1180250.793      9347.610     32412.186     41759.797  
         29.000   1147588.763      9097.767     32662.030     41759.797  
         30.000   1114674.963      8845.997     32913.800     41759.797  
         31.000   1081507.453      8592.286     33167.510     41759.797  
         32.000   1048084.276      8336.620     33423.177     41759.797  
         33.000   1014403.463      8078.983     33680.814     41759.797  
         34.000    980463.026      7819.360     33940.437     41759.797  
         35.000    946260.965      7557.736     34202.061     41759.797  
         36.000    911795.264      7294.095     34465.702     41759.797  
         37.000    877063.889      7028.422     34731.375     41759.797  
         38.000    842064.793      6760.701     34999.096     41759.797  
         39.000    806795.913      6490.916     35268.880     41759.797  
         40.000    771255.168      6219.052     35540.745     41759.797  
         41.000    735440.463      5945.092     35814.705     41759.797  
         42.000    699349.687      5669.020     36090.776     41759.797  
         43.000    662980.711      5390.821     36368.976     41759.797  
         44.000    626331.390      5110.476     36649.320     41759.797  
         45.000    589399.565      4827.971     36931.825     41759.797  
         46.000    552183.057      4543.288     37216.508     41759.797  
         47.000    514679.671      4256.411     37503.386     41759.797  
         48.000    476887.197      3967.322     37792.474     41759.797  
         49.000    438803.406      3676.005     38083.791     41759.797  
         50.000    400426.052      3382.443     38377.354     41759.797  
         51.000    361752.873      3086.617     38673.179     41759.797  
         52.000    322781.588      2788.512     38971.285     41759.797  
         53.000    283509.900      2488.108     39271.689     41759.797  
         54.000    243935.492      2185.389     39574.408     41759.797  
         55.000    204056.031      1880.336     39879.461     41759.797  
         56.000    163869.167      1572.932     40186.865     41759.797  
         57.000    123372.528      1263.158     40496.638     41759.797  
         58.000     82563.728       950.997     40808.800     41759.797  
         59.000     41440.360       636.429     41123.368     41759.797  
         60.000         0.000       319.436     41440.360     41759.797  

(%i4) quit();

If you want to be a little stylish in your monthly payments, that is, instead of equal payments, you want to do increasing payments, Maxima could help you with that as well. arit_amortization() and geo_amortization() are two such functions, which provides the schedule for increasing payments with fixed amount increments and fixed rate increments, respectively. Here’s a small demo of the same:

$ maxima -q
(%i1) load(finance)$
(%i2) amortization(0.10, 100, 5)$
           "n"       "Balance"     "Interest"   "Amortization"  "Payment"      
          0.000       100.000         0.000         0.000         0.000  
          1.000        83.620        10.000        16.380        26.380  
          2.000        65.603         8.362        18.018        26.380  
          3.000        45.783         6.560        19.819        26.380  
          4.000        23.982         4.578        21.801        26.380  
          5.000         0.000         2.398        23.982        26.380  

(%i3) arit_amortization(0.10, 10, 100, 5)$
           "n"       "Balance"     "Interest"   "Amortization"  "Payment"      
          0.000       100.000         0.000         0.000         0.000  
          1.000       101.722        10.000        -1.722         8.278  
          2.000        93.615        10.172         8.106        18.278  
          3.000        74.698         9.362        18.917        28.278  
          4.000        43.890         7.470        30.809        38.278  
          5.000         0.000         4.389        43.890        48.278  

(%i4) geo_amortization(0.10, 0.05, 100, 5)$
           "n"       "Balance"     "Interest"   "Amortization"  "Payment"      
          0.000       100.000         0.000         0.000         0.000  
          1.000        85.907        10.000        14.093        24.093  
          2.000        69.200         8.591        16.707        25.298  
          3.000        49.558         6.920        19.642        26.562  
          4.000        26.623         4.956        22.935        27.891  
          5.000         0.000         2.662        26.623        29.285  

(%i5) quit();

%i2 has been provided for comparative analysis. %i3 shows the incremental payout with increments of ₹10 (the second parameter of arit_amortization()). %i4 shows the incremental payout with increments at the rate of 5% (the second parameter of geo_amortization()). Both these computations could be done in decrements as well – just pass the second parameter negative.

Plan your savings

Say, you have a savings account like PPF (public provident fund), giving you interest at a rate of 8% p.a., and at the end of 5 years, you want to have save ₹1,00,000. So, what should be your minimum yearly deposit into your account. It is not just divide by 5, as interest would be also added to your savings. saving() shows you the complete schedule as follows:

$ maxima -q
(%i1) load(finance)$
(%i2) saving(0.08 /* interest rate */, 100000 /* final savings */, 5 /* years */)$
           "n"       "Balance"     "Interest"    "Payment"      
          0.000          0.000         0.000         0.000  
          1.000      17045.645         0.000     17045.645  
          2.000      35454.943      1363.652     17045.645  
          3.000      55336.983      2836.395     17045.645  
          4.000      76809.588      4426.959     17045.645  
          5.000     100000.000      6144.767     17045.645  

And, the minimum yearly deposit to be done is ₹17,046. The “Balance” and “Interest” columns, respectively, tell you about the balance and the interest accumulated in the corresponding year. If you are only interested in knowing the minimum amount to be deposited, you may just use the annuity_fv() function – basically computing the annuity of ₹17,046 every year for 5 years to have a future saving of ₹1,00,000 after 5 years.

(%i3) annuity_fv(0.08, 100000, 5);
(%o3)                         17045.64545668365
(%i4) quit();

Project planning

Finance management is a key ingredient of any project planning, whether it be a professional or personal project. Assume a project would take n years, with given yearly expenses, and say the available interest rate is r p.a. Then, a common question, every project manager needs to answer is what is the net present value (NPV) of the project, which needs to be invested for the project. The answer to this basic question is more often than not, one of the important factors for deciding whether to take up this project or not. Maxima provides npv() to compute the same. As an example, if a project needs ₹100, ₹200, ₹150, ₹600 over 4 years, respectively, and the current interest rate is 7%, what is the NPV? It would be ₹848 as shown below:

$ maxima -q
(%i1) load(finance)$
(%i2) npv(0.07, [100, 200, 150, 600]);
(%o2)                         848.3274983420189
(%i3) quit();

Another common practice to select between various projects is to compute the benefit to cost ratio of the various projects, and select the one with best ratio. The benefit to cost ratio for a given interest rate r could be computed using benefit_cost(). Here’s an example to demonstrate the same, assuming 18% as the rate of interest:

  • Project P1 (2 years): Yearly Benefits (100, 200), Yearly Costs (150, 50)
  • Project P2 (3 years): Yearly Benefits (0, 200, 100), Yearly Costs (100, 100, 0)
  • Project P3 (4 years): Yearly Benefits (0, 200, 200, 100), Yearly Costs (100, 100, 50, 50)
$ maxima -q
(%i1) load(finance)$
(%i2) benefit_cost(0.18, [100, 200], [150, 50]);
(%o2)                         1.400881057268722
(%i3) benefit_cost(0.18, [0, 200, 100], [100, 100, 0]);
(%o3)                         1.306173223448919
(%i4) benefit_cost(0.18, [0, 200, 200, 100], [100, 100, 50, 50]);
(%o4)                         1.489492494361802
(%i5) quit();

And clearly, over the long run the 4-year project P3 has better benefit cost ratio. But if only looking for shorter term benefits, then one may even go for project P1 as well.

Twenty-third Article >>

   Send article as PDF