Monthly Archives: April 2014

Disk on RAM: Playing destructively

This fifteenth article, which is part of the series on Linux device drivers, experiments with a dummy hard disk on RAM to demonstrate the block drivers.

<< Fourteenth Article

Play first, rules later

After a delicious lunch, theory makes audience sleepy. So, let’s start with the code itself. Code demonstrated is available at dor_code.tar.bz2. This tar ball contains 3 ‘C’ source files, 2 ‘C’ headers, and a Makefile. As usual, executing make will build the ‘disk on ram’ driver (dor.ko) – this time combining the 3 ‘C’ files. Check out the Makefile to see how. make clean would do the usual clean of the built stuff.

Once built, the following are the experimenting steps (Refer to Figures 25, 26, 27):

  • Load the driver dor.ko using insmod. This would create the block device files representing the disk on 512 KibiBytes (KiB) of RAM, with 3 primary and 3 logical partitions.
  • Checkout the automatically created block device files (/dev/rb*). /dev/rb is the entire disk of 512 KiB size. rb1, rb2, rb3 are the primary partitions with rb2 being the extended partition and containing the 3 logical partitions rb5, rb6, rb7.
  • Read the entire disk (/dev/rb) using the disk dump utility dd.
  • Zero out the first sector of the disk’s first partition (/dev/rb1) again using dd.
  • Write some text into the disk’s first partition (/dev/rb1) using cat.
  • Display the initial contents of the first partition (/dev/rb1) using the xxd utility. See Figure 26 for the xxd output.
  • Display the partition info for the disk using fdisk. See Figure 27 for the fdisk output.
  • (Quick) Format the third primary partition (/dev/rb3) as vfat filesystem (like your pen drive), using mkfs.vfat (Figure 27).
  • Mount the newly formatted partition using mount, say at /mnt (Figure 27).
  • Disk usage utility df would now show this partition mounted at /mnt (Figure 27). You may go ahead and store your files there. But, please remember that these partitions are all on a disk on RAM, and so non-persistent. Hence,
  • Unloading the driver using ‘rmmod dor‘ would vanish everything. Though the partition needs to be unmounted using ‘umount /mnt‘ before doing that.

Please note that all the above experimenting steps need to be executed with root privileges.

Figure 25: Playing with 'Disk on RAM' driver

Figure 25: Playing with ‘Disk on RAM’ driver

Figure 26: xxd showing the initial data on the first partition (/dev/rb1)

Figure 26: xxd showing the initial data on the first partition (/dev/rb1)

Figure 27: Formatting the third partition (/dev/rb3)

Figure 27: Formatting the third partition (/dev/rb3)

Now, let’s learn the rules

We have just now played around with the disk on RAM but without actually knowing the rules, i.e. the internal details of the game. So, let’s dig into the nitty-gritties to decode the rules. Each of the three .c files represent a specific part of the driver. ram_device.c and ram_device.h abstract the underlying RAM operations like vmalloc/vfree, memcpy, etc, providing disk operation APIs like init/cleanup, read/write, etc. partition.c and partition.h provide the functionality to emulate the various partition tables on the disk on RAM. Recall the pre-lunch session (i.e. the previous article) to understand the details of partitioning. The code in this is responsible for the partition information like number, type, size, etc that is shown up on the disk on RAM using fdisk. ram_block.c is the core block driver implementation exposing the disk on RAM as the block device files (/dev/rb*) to the user-space. In other words, the four files ram_device.* and partition.* form the horizontal layer of the device driver and ram_block.c forms the vertical (block) layer of the device driver. So, let’s understand that in detail.

The block driver basics

Conceptually, the block drivers are very similar to character drivers, especially with regards to the following:

  • Usage of device files
  • Major and minor numbers
  • Device file operations
  • Concept of device registration

So, if one already knows character driver implementations, it would be similar to understand the block drivers. Though, they are definitely not identical. The key differences could be listed out as follows:

  • Abstraction for block-oriented versus byte-oriented devices
  • Block drivers are designed to be used by I/O schedulers, for optimal performance. Compare that with character drivers to be used by VFS.
  • Block drivers are designed to be integrated with the Linux’ buffer cache mechanism for efficient data access. Character drivers are pass-through drivers, accessing the hardware directly.

And these trigger the implementation differences. Let’s analyze the key code snippets from ram_block.c, starting at the driver’s constructor rb_init().

First step is to register for a 8-bit (block) major number. And registering for that implicitly means registering for all the 256 8-bit minor numbers associated with that. The function for that is:

int register_blkdev(unsigned int major, const char *name);

major is the major number to be registered. name is a registration label displayed under the kernel window /proc/devices. Interestingly, register_blkdev() tries to allocate & register a freely available major number, when 0 is passed for its first parameter major; and on success, the allocated major number is returned. The corresponding deregistration function is:

void unregister_blkdev(unsigned int major, const char *name);

Both are prototyped in <linux/fs.h>

Second step is to provide the device file operations, through the struct block_device_operations (prototyped in <linux/blkdev.h>) for the registered major number device files. However, these operations are too few compared to the character device file operations, and mostly insignificant. To elaborate, there are no operations even to read and write. That’s surprising. But as we already know that the block drivers need to integrate with the I/O schedulers, the read-write implementation is achieved through something called request queues. So, along with providing the device file operations, the following needs to provided:

  • Request queue for queuing the read/write requests
  • Spin lock associated with the request queue for its concurrent access protection
  • Request function to process the requests queued in the request queue

Also, there is no separate interface for block device file creations, so the following are also provided:

  • Device file name prefix, commonly referred as disk_name (“rb” in the dor driver)
  • Starting minor number for the device files, commonly referred as the first_minor

Finally, two block device-specific things are also provided along with the above, namely:

  • Maximum number of partitions supported for this block device, by specifying the total minors
  • Underlying device size in units of 512-byte sectors, for the logical block access abstraction

All these are registered through the struct gendisk using the function:

void add_disk(struct gendisk *disk);

The corresponding delete function is:

void del_gendisk(struct gendisk *disk);

Prior to add_disk(), the various fields of struct gendisk need to be initialized, either directly or using various macros/functions like set_capacity(). major, first_minor, fops, queue, disk_name are the minimal fields to be initialized directly. And even before the initialization of these fields, the struct gendisk needs to be allocated using the function:

struct gendisk *alloc_disk(int minors);

where minors is the total number of partitions supported for this disk. And the corresponding inverse function would be:

void put_disk(struct gendisk *disk);

All these are prototyped in <linux/genhd.h>.

Request queue and its request processing function

The request queue also needs to be initialized and set up into the struct gendisk, before the add_disk(). The request queue is initialized by calling:

struct request_queue *blk_init_queue(request_fn_proc *, spinlock_t *);

providing the request processing function and the initialized concurrency protection spinlock, as its parameters. The corresponding queue cleanup function is:

void blk_cleanup_queue(struct request_queue *);

The request (processing) function should be defined with the following prototype:

void request_fn(struct request_queue *q);

And it should be coded to fetch a request from its parameter q, say using

struct request *blk_fetch_request(struct request_queue *q);

and then either process it or initiate the processing. Whatever it does, it should be non-blocking, as this request function is called from a non-process context, and also after taking the queue’s spinlock. So, moreover only the functions not releasing or taking the queue’s spinlock should be used within the request function.

A typical request processing as demonstrated by the function rb_request() in ram_block.c is:

while ((req = blk_fetch_request(q)) != NULL) /* Fetching a request */
{
	/* Processing the request: the actual data transfer */
	ret = rb_transfer(req); /* Our custom function */
	/* Informing that the request has been processed with return of ret */
	__blk_end_request_all(req, ret);
}

Request and its processing

rb_transfer() is our key function, which parses a struct request and accordingly does the actual data transfer. The struct request mainly contains the direction of data transfer, starting sector for the data transfer, total number of sectors for the data transfer, and the scatter-gather buffer for data transfer. The various macros to extract these information from the struct request are as follows:

rq_data_dir(req); /* Operation: 0 - read from device; otherwise - write to device */
blk_req_pos(req); /* Starting sector to process */
blk_req_sectors(req); /* Total sectors to process */
rq_for_each_segment(bv, req, iter) /* Iterator to extract individual buffers */

rq_for_each_segment() is the special one which iterates over the struct request (req) using iter, and extracting the individual buffer information into the struct bio_vec (bv: basic input/output vector) on each iteration. And, then on each extraction, the appropriate data transfer is done, based on the operation type, invoking one of the following APIs from ram_device.c:

void ramdevice_write(sector_t sector_off, u8 *buffer, unsigned int sectors);
void ramdevice_read(sector_t sector_off, u8 *buffer, unsigned int sectors);

Check out the complete code of rb_transfer() in ram_block.c

Summing up

“With that, we have actually learnt the beautiful block drivers by traversing through the design of a hard disk, and playing around with partitioning, formatting, and various other raw operations on a hard disk. Thanks for your patient listening. Now, the session is open for questions. Or, you may post your queries as comments, below.”

Sixteenth Article >>

   Send article as PDF   

Expression Simplification using Maxima

This fifteenth article of the mathematical journey through open source, demonstrates the various techniques of expression simplification using Maxima.

<< Fourteenth Article

Expression simplification can be done in a variety of ways. Let’s start with the simple ones, and then move onto more powerful ones.

Real number simplification

A simple simplification is to convert a given number into a rational number using ratsimp(). Below follows the demonstration.

$ maxima -q
(%i1) ratsimp(9);
(%o1)                                  9
(%i2) ratsimp(10.0);
rat: replaced 10.0 by 10/1 = 10.0
(%o2)                                 10
(%i3) string(ratsimp(4.2)); /* string to print it on one line */
rat: replaced 4.2 by 21/5 = 4.2
(%o3)                               21/5
(%i4) string(factor(3.2)); /* string to print it on one line */
rat: replaced 3.2 by 16/5 = 3.2
(%o4)                                2^4/5
(%i5) string(ratsimp(4.3333)); /* string to print it on one line */
rat: replaced 4.3333 by 43333/10000 = 4.3333
(%o5)                            43333/10000
(%i6) string(ratsimp(4.3333333)); /* string to print it on one line */
rat: replaced 4.3333333 by 13/3 = 4.333333333333333
(%o6)                               13/3
(%i7) quit();

Another one is to check whether a number is an integer using askinteger(). And if yes, is it an even or odd number, again using askinteger(). Moreover, asksign() checks for the sign. In case of trying these with unknown variables, Maxima would ask the user the necessary question(s) to deduce the response, and store it for future analysis. For example, askinteger(x) would ask us if x is an integer. And, if we say yes, it can then deduce many more information by itself. Below are some examples:

$ maxima -q
(%i1) askinteger(1);
(%o1)                                 yes
(%i2) askinteger(1.0);
rat: replaced 1.0 by 1/1 = 1.0
(%o2)                                 yes
(%i3) askinteger(1.2);
rat: replaced 1.2 by 6/5 = 1.2
(%o3)                                 no
(%i4) askinteger(-9);
(%o4)                                 yes
(%i5) askinteger(2/3 + 3/4 + 1/6 + 5/12);
(%o5)                                 yes
(%i6) askinteger(-9, even);
(%o6)                                 no
(%i7) askinteger(0, even);
(%o7)                                 yes
(%i8) properties(x);
(%o8)                                []
(%i9) askinteger(x);
Is x an integer?
yes; /* This is our response */
(%o9)                                 yes
(%i10) askinteger(x + 9);
(%o10)                                 yes
(%i11) askinteger(2 * x, even);
(%o11)                                yes
(%i12) askinteger(2 * x + 1, even);
(%o12)                                no
(%i13) askinteger(x, even);
Is x an even number?
n; /* This is our response */
(%o13)                                no
(%i14) askinteger(x, odd);
(%o14)                                yes
(%i15) askinteger(x^3 - (x + 1)^2, even);
(%o15)                                no
(%i16) properties(x);
(%o16)          [database info, kind(x, integer), kind(x, odd)]
(%i17) asksign((-1)^x);
(%o17)                                neg
(%i18) asksign((-1)^(x+1));
(%o18)                                pos
(%i19) asksign((-1)^x+1);
(%o19)                               zero
(%i20) quit();

Maxima simplification uses the concept of properties of symbols. As an example, note the properties of x in the above demonstration at %i8 and %i16.

Complex number simplification

Complex numbers have two common useful forms, namely the exponential and the circular (with sine & cosine) forms. demoivre() converts the exponential to circular form and exponentialize() does the other way round. Using expand() along with them, can simplify complicated looking expressions. Here goes few examples:

$ maxima -q
(%i1) string(demoivre(exp(%i*x^2))); /* %i is sqrt(-1) */
(%o1)                       %i*sin(x^2)+cos(x^2)
(%i2) string(exponentialize(a*(cos(t)))); /* %i is sqrt(-1) */
(%o2)                    a*(%e^(%i*t)+%e^-(%i*t))/2
(%i3) string(expand(exponentialize(a*(cos(t)+%i*sin(t))))); /* %i is sqrt(-1) */
(%o3)                            a*%e^(%i*t)
(%i4) quit();

Expansions and Reductions

As already seen in the previous article, expand() expands an expression completely, by default. However, it can be controlled by specifying the maximum power to which to expand for both the numerator and the denominator, respectively. Using factor() can compact the expanded expressions. Moreover, in many cases, we would like to expand it only with respect to only some variable(s). Say, (x + a + b)^2 should be expanded with respect to x. expandwrt() is meant exactly for that. One example of each of these is shown below.

$ maxima -q
(%i1) string(expand(((x+1)^2-x^2)/(x+1)^2, 2, 0));
(%o1)                      2*x/(x+1)^2+1/(x+1)^2
(%i2) string(factor(((x+1)^2-x^2)/(x+1)^2));
(%o2)                           (2*x+1)/(x+1)^2
(%i3) string(expandwrt((x+a+b)^2,x));
(%o3)                      x^2+2*(b+a)*x+(b+a)^2
(%i4) quit();

Expressions containing logs, exponentials, radicals (powers) can be simplified using radcan(). Rule based simplifications can be achieved using sequential comparative simplification function scsim(). Both of these call for a few examples.

$ maxima -q
(%i1) string(radcan(exp(5 * log(x) + log(3 * exp(log(y) / 4)))));
(%o1)                          3*x^5*y^(1/4)
(%i2) radcan((log(2*x+2*x^2)-log(x))/(log(1+1/x)+log(2*x)));
(%o2)                                1
(%i3) expr: a^2 + b^2 + c^2$
(%i4) eq1: a^2 + 2*a*b + b^2 = 4$
(%i5) eq2: a * b = 6$
(%i6) string(scsimp(expr, eq1, eq2));
(%o6)                              c^2-8
(%i7) quit();

Unlike Octave, Maxima by default doesn’t evaluate its expressions, it only simplifies. What it means is that expressions with integers like cos(1), exp(2), sqrt(3), etc. may remain as is in the most simplified form, instead of evaluating to their respective float numerical values. In such cases, we may force the evaluation by passing the option numer. Similar evaluation can be achieved for predicates, using pred.

$ maxima -q
(%i1) cos(1);
(%o1)                             cos(1)
(%i2) cos(1), numer;
(%o2)                        .5403023058681398
(%i3) sqrt(7);
(%o3)                             sqrt(7)
(%i4) sqrt(7), numer;
(%o4)                        2.645751311064591
(%i4) 1 + 2 > 9;
(%o4)                              3 > 9
(%i5) 1 + 2 > 9, pred;
(%o5)                              false
(%i6) string(%e^%pi < %pi^%e); /* string to print it on one line */
(%o6)                         %e^%pi < %pi^%e
(%i7) %e^%pi < %pi^%e, pred;
(%o7)                              false
(%i8) quit();

Summation Simplifications

Symbolical representation and manipulations of summations can be beautifully achieved using sum() and the option simpsum. Check out the code execution below:

$ maxima -q
(%i1) sum(a * i, i, 1, 5);
(%o1)                                15 a
(%i2) sum(a, i, 1, 5);
(%o2)                                 5 a
(%i3) sum(a * i, i, 1, n);
                                      n
                                     ====
                                     \
(%o3)                              a  >    i
                                     /
                                     ====
                                     i = 1
(%i4) simpsum: true$ /* Enable simplification of summations */
(%i5) string(sum(a * i, i, 1, n)); /* string to print it on one line */
(%o5)                            a*(n^2+n)/2
(%i6) string(sum(i^2 - i, i, 1, n) + sum(j, j, 1, n));
(%o6)                         (2*n^3+3*n^2+n)/6
(%i7) string(factor(sum(i^2 - i, i, 1, n) + sum(j, j, 1, n)));
(%o7)                         n*(n+1)*(2*n+1)/6
(%i8) quit();

Sixteenth Article >>

   Send article as PDF