Monthly Archives: October 2014

The Semester Project – Part IV: Formatting a Pen Drive

This twenty-first article, which is part of the series on Linux device drivers, takes the next step towards writing a file system module by writing a formatting application for your real pen drive.

<< Twentieth Article

Thanks friends for your confidence in Shweta and not trying to help her out in figuring out the issues with her code. She indeed figured out and fixed the following issues in her code:

  • sfs_read() and sfs_write() need to check for the read and write file permissions before proceeding to read and write, respectively
  • sfs_write() should free any previously allocated blocks, as write is always over-write
  • Moreover, the earlier written sfs_remove() also, now needs to free up the allocated blocks

SFS Format for a real partition

There after Pugs took the lead and slightly modified Shweta’s format_sfs.c and sfs_ds.h files to format a real pen drive’s partition. The key change is that instead of creating the default regular file .sfsf to format, now it would be operating on an existing block device file corresponding to an underlying partition, say something like /dev/sdb1. So,

  • It would get the partition’s size from the partition’s block device file itself, rather than taking it as a command-line argument
  • Accordingly, it would now expect the partition’s block device file name instead of size, as main()‘s first argument.
  • Also, it would not need the mark_data_block() to grow the file equal to the partition size

The ioctl command BLKGETSIZE64 gets the 64-bit size of the underlying block device partition, in bytes. Then, it is divided by the block size (SIMULA_FS_BLOCK_SIZE) to get the partition’s size in block units. Here is the corresponding modified snippet of the main() function in format_real_sfs.c (updated format_sfs.c), along with the required typedef in real_sfs_ds.h (updated sfs_ds.h). (Note: For readability, Pugs renamed all uint* by byte*):

typedef unsigned long long byte8_t;
...
byte8_t size;

sfs_handle = open(argv[1], O_RDWR);
if (sfs_handle == -1)
{
	fprintf(stderr, "Error formatting %s: %s\n", argv[1], strerror(errno));
	return 2;
}
if (ioctl(sfs_handle, BLKGETSIZE64, &size) == -1)
{
	fprintf(stderr, "Error getting size of %s: %s\n", argv[1], strerror(errno));
	return 3;
}
sb.partition_size = size / SIMULA_FS_BLOCK_SIZE;

As per the above code, the following additional header files need to be included:

#include <errno.h> /* For errno */
#include <string.h> /* For strerror() */
#include <sys/ioctl.h> /* For ioctl() */
#include <linux/fs.h> /* For BLKGETSIZE64 */

With all the above changes compiled into format_real_sfs, Pugs plugged in his pen drive, partition of which got auto mounted. Then, he took backup of its content and unmounted the same – ready for a real SFS format of the pen drive partition.

Caution: Take a backup of your pen drive’s content – you are formatting it for real. Be careful in choosing the right partition of your pen drive. Otherwise, you may forever lose data from your hard disk or even make your system un-bootable. You have been warned.

Figure 36: Formatting the pen drive

Figure 36: Formatting the pen drive

Figure 36 demonstrates all the above but backup steps at root prompt #. Instead, one may use sudo, as well. Note that Pugs got his pen drive partition mounted at /media/10AC-BF1C, and the corresponding device file is /dev/sdb1 (/dev/sdb being the complete pen drive). You may have both these differently. Accordingly, follow the steps for yourself. Also, note that, the real SFS formatting is then started using the following command:

# ./format_real_sfs /dev/sdb1

And then, there is a ^C (Ctrl-C) immediately after that, basically terminating the formatting. Aha! Did Pugs realize something important was there on the pen drive? Not really, as his pen drive is already empty. Actually, what happened is that formatting was going on for quite some time – so Pugs had some doubt about his code changes and so he terminated it. Reviewing his code didn’t yield much, so he reissued the formatting, this time with the time command, to figure out exactly how much time is the formatting taking and then may be debug/fix that. And finally! The formatting is complete but after a whopping 430.88 seconds (7+ minutes), yes minutes. time basically shows the real time taken (includes the time when other processes has been running after context switch), time executed in user space, time executed in kernel space. That’s huge – something needs optimization. And it didn’t take much time for a close review to undermine the issue. The key time taker code would be the clear_file_entries() function. Right now its clearing the file entries one by one, i.e. writing 64-byte sized file entries one by one – that’s pretty non-optimal. A better approach would be to fill up a block with such entries, and then write these blocks one by one. In case of a 512-byte block (i.e. SIMULA_FS_BLOCK_SIZE defined as 512), that would mean 8 file entries in a 512-byte block and then writing these 512-byte blocks one by one. So, Pugs changed the clear_file_entries() function to do the same, and viola! formatting is complete in a little less than 26 seconds. Here’s the answer to your curiosity – the re-written clear_file_entries() function:

void clear_file_entries(int sfs_handle, sfs_super_block_t *sb)
{
	int i;
	byte1_t block[SIMULA_FS_BLOCK_SIZE];

	for (i = 0; i < sb->block_size / sb->entry_size; i++)
	{
		memcpy(block + i * sb->entry_size, &fe, sizeof(fe));
	}
	for (i = 0; i < sb->entry_table_size; i++)
	{
		write(sfs_handle, block, sizeof(block));
	}
}

Now, you may plug out and plug in the pen drive back. And you may wonder that neither it is auto-mounted, nor you are able to mount it. That’s expected, as now it is formatted with a file system which is not yet coded as (kernel) module and there is no one in the kernel to decode the same. So, coding that kernel module would be the ultimate step to get everything working like with any other existing file systems (vfat, ext3, …). If you are worried that your pen drive is spoiled, you may re-format it with the FAT32 (vfat) file system as follows (as root or with sudo):

# mkfs.vfat /dev/sdb1 # Be careful with the correct partition device file

and then plug out & plug in the pen drive to get auto-mounted. But, you know Pugs being a cool carefree guy, instead went ahead to try out browsing the Simula file system created on the pen drive partition.

Browsing the pen drive partition

Obviously, there were slight modifications to the browse_sfs.c application as well, in line with the changes to format_sfs.c. Major one being compulsorily taking the partition’s device file to browse as the command-line argument, instead of browsing the default regular file .sfsf.

All the updated files (real_sfs_ds.h, format_real_sfs.c, browse_real_sfs.c and Makefile) are available from rsfs_code.tar.bz2.

Figure 37: SFS browser on pen drive

Figure 37: SFS browser on pen drive

Figure 37 shows the browser in action. However, the coolest browsing would be the same way as is done with all other file systems, using the shell commands cd, ls, … Yes, and for that we would need the real SFS module in place. Keep following what’s Pugs upto for getting that in place.

Twenty-second Article >>

   Send article as PDF   

Laplace Transforms: Solving Engineering Problems

This twenty-first article of the mathematical journey through open source, demonstrates the Laplace transforms through Maxima.

<< Twentieth Article

In higher mathematics, transforms play an important role. A transform is mathematical logic to transform or convert a mathematical expression into another mathematical expression, typically from one domain to another. Laplace and Fourier are two very common examples, transforming from time domain to frequency domain. In general, such transforms have their corresponding inverse transforms. And this combination of direct and inverse transforms is very powerful in solving many real life engineering problems. Focus of this article is Laplace and its inverse transform, along with some problem solving highlights.

Laplace transform

Mathematically, Laplace transform F(s) of a function f(t) is defined as follows:

F(s) = \int_0^\infty{f(t) * exp(-s*t) dt},

where t represents time and s represents complex angular frequency.

To demonstrate it, let’s take a simple example of f(t) = 1. Substituting and integrating, we get F(s) = 1/s. Maxima has the function laplace() to do the same. In fact, with that, we can choose to let our variables t and s be anything else as well. But, as per our mathematical notations, preserving them as t and s would be the most appropriate. Let’s start with some basic Laplace transforms:
(Note that string() has been used to just flatten the expression)

$ maxima -q
(%i1) string(laplace(1, t, s));
(%o1)                                 1/s
(%i2) string(laplace(t, t, s));
(%o2)                                1/s^2
(%i3) string(laplace(t^2, t, s));
(%o3)                                2/s^3
(%i4) string(laplace(t+1, t, s));
(%o4)                              1/s+1/s^2
(%i5) string(laplace(t^n, t, s));
Is  n + 1  positive, negative, or zero?

p; /* Our input */
(%o5)                         gamma(n+1)*s^(-n-1)
(%i6) string(laplace(t^n, t, s));
Is  n + 1  positive, negative, or zero?

n; /* Our input */
(%o6)                  gamma_incomplete(n+1,0)*s^(-n-1)
(%i7) string(laplace(t^n, t, s));
Is  n + 1  positive, negative, or zero?

z; /* Our input, making it non-solvable */
(%o7)                          'laplace(t^n,t,s)
(%i8) string(laplace(1/t, t, s)); /* Non-solvable */
(%o8)                          'laplace(1/t,t,s)
(%i9) string(laplace(1/t^2, t, s)); /* Non-solvable */
(%o9)                         'laplace(1/t^2,t,s)
(%i10) quit();

Note that, in the above examples, the expression is preserved as is, in case of non-solvability.

laplace() is designed to understand various symbolic functions, such as sin(), cos(), sinh(), cosh(), log(), exp(), delta(), erf(). delta() is Dirac delta function, and erf() is the error function – others being the usual mathematical functions.

$ maxima -q
(%i1) string(laplace(sin(t), t, s));
(%o1)                              1/(s^2+1)
(%i2) string(laplace(sin(w*t), t, s));
(%o2)                             w/(w^2+s^2)
(%i3) string(laplace(cos(t), t, s));
(%o3)                              s/(s^2+1)
(%i4) string(laplace(cos(w*t), t, s));
(%o4)                             s/(w^2+s^2)
(%i5) string(laplace(sinh(t), t, s));
(%o5)                              1/(s^2-1)
(%i6) string(laplace(sinh(w*t), t, s));
(%o6)                            -w/(w^2-s^2)
(%i7) string(laplace(cosh(t), t, s));
(%o7)                              s/(s^2-1)
(%i8) string(laplace(cosh(w*t), t, s));
(%o8)                            -s/(w^2-s^2)
(%i9) string(laplace(log(t), t, s));
(%o9)                         (-log(s)-%gamma)/s
(%i10) string(laplace(exp(t), t, s));
(%o10)                              1/(s-1)
(%i11) string(laplace(delta(t), t, s));
(%o11)                                 1
(%i12) string(laplace(erf(t), t, s));
(%o12)                     %e^(s^2/4)*(1-erf(s/2))/s
(%i13) quit();

Interpreting the transform

A Laplace transform is typically a fractional expression consisting of a numerator and a denominator. Solving the denominator by equating it to zero, gives the various complex frequencies associated with the original function. These are called the poles of the function. For example, the Laplace transform of sin(w * t) is w/(s^2 + w^2), where the denominator is s^2 + w^2. Equating that to zero and solving it, gives complex frequency s = +iw, -iw; thus indicating that the frequency of the original expression sin(w * t) is w, which indeed is w. Here goes few demonstrations for the same:

$ maxima -q
(%i1) string(laplace(sin(w*t), t, s));
(%o1)                             w/(w^2+s^2)
(%i2) string(denom(laplace(sin(w*t), t, s))); /* The Denominator */
(%o2)                               w^2+s^2
(%i3) string(solve(denom(laplace(sin(w*t), t, s)), s)); /* The Poles */
(%o3)                        [s = -%i*w,s = %i*w]
(%i4) string(solve(denom(laplace(sinh(w*t), t, s)), s));
(%o4)                           [s = -w,s = w]
(%i5) string(solve(denom(laplace(cos(w*t), t, s)), s));
(%o5)                        [s = -%i*w,s = %i*w]
(%i6) string(solve(denom(laplace(cosh(w*t), t, s)), s));
(%o6)                           [s = -w,s = w]
(%i7) string(solve(denom(laplace(exp(w*t), t, s)), s));
(%o7)                               [s = w]
(%i8) string(solve(denom(laplace(log(w*t), t, s)), s));
(%o8)                               [s = 0]
(%i9) string(solve(denom(laplace(delta(w*t), t, s)), s));
(%o9)                                 []
(%i10) string(solve(denom(laplace(erf(w*t), t, s)), s));
(%o10)                              [s = 0]
(%i11) quit();

Involved Laplace transforms

laplace() also understands derivative() / diff(), integrate(), sum(), and ilt() – the inverse Laplace transform. Here are some interesting transforms showing the same:

$ maxima -q
(%i1) laplace(f(t), t, s);
(%o1)                         laplace(f(t), t, s)
(%i2) string(laplace(derivative(f(t), t), t, s));
(%o2)                      s*'laplace(f(t),t,s)-f(0)
(%i3) string(laplace(integrate(f(x), x, 0, t), t, s));
(%o3)                        'laplace(f(t),t,s)/s
(%i4) string(laplace(derivative(sin(t), t), t, s));
(%o4)                              s/(s^2+1)
(%i5) string(laplace(integrate(sin(t), t), t, s));
(%o5)                             -s/(s^2+1)
(%i6) string(sum(t^i, i, 0, 5));
(%o6)                         t^5+t^4+t^3+t^2+t+1
(%i7) string(laplace(sum(t^i, i, 0, 5), t, s));
(%o7)                1/s+1/s^2+2/s^3+6/s^4+24/s^5+120/s^6
(%i8) string(laplace(ilt(1/s, s, t), t, s));
(%o8)                                 1/s
(%i9) quit();

Note the usage of ilt() – inverse Laplace transform in the %i8 of above example. Calling laplace() and ilt() one after the other cancels their effect – that is what is meant by inverse. Let’s look into some common inverse Laplace transforms.

Inverse Laplace transforms

$ maxima -q
(%i1) string(ilt(1/s, s, t));
(%o1)                                  1
(%i2) string(ilt(1/s^2, s, t));
(%o2)                                  t
(%i3) string(ilt(1/s^3, s, t));
(%o3)                                t^2/2
(%i4) string(ilt(1/s^4, s, t));
(%o4)                                t^3/6
(%i5) string(ilt(1/s^5, s, t));
(%o5)                               t^4/24
(%i6) string(ilt(1/s^10, s, t));
(%o6)                             t^9/362880
(%i7) string(ilt(1/s^100, s, t));
(%o7) t^99/9332621544394415268169923885626670049071596826438162146859296389521759999
	3229915608941463976156518286253697920827223758251185210916864000000000000000
	0000000
(%i8) string(ilt(1/(s-a), s, t));
(%o8)                              %e^(a*t)
(%i9) string(ilt(1/(s^2-a^2), s, t));
(%o9)                   %e^(a*t)/(2*a)-%e^-(a*t)/(2*a)
(%i10) string(ilt(s/(s^2-a^2), s, t));
(%o10)                      %e^(a*t)/2+%e^-(a*t)/2
(%i11) string(ilt(1/(s^2+a^2), s, t));
Is  a  zero or nonzero?

n; /* Our input */
(%o11)                            sin(a*t)/a
(%i12) string(ilt(s/(s^2+a^2), s, t));
Is  a  zero or nonzero?

n; /* Our input */
(%o12)                             cos(a*t)
(%i13) assume(a < 0) or assume(a > 0)$
(%i14) string(ilt(1/(s^2+a^2), s, t));
(%o14)                             sin(a*t)/a
(%i15) string(ilt(s/(s^2+a^2), s, t));
(%o15)                              cos(a*t)
(%i16) string(ilt((s^2+s+1)/(s^3+s^2+s+1), s, t));
(%o16)                      sin(t)/2+cos(t)/2+%e^-t/2
(%i17) string(laplace(sin(t)/2+cos(t)/2+%e^-t/2, t, s));
(%o17)               s/(2*(s^2+1))+1/(2*(s^2+1))+1/(2*(s+1))
(%i18) string(rat(laplace(sin(t)/2+cos(t)/2+%e^-t/2, t, s)));
(%o18)                       (s^2+s+1)/(s^3+s^2+s+1)
(%i19) quit();

Observe that if we take the Laplace transform of the above %o outputs, they would give back the expressions, which are input to ilt() of the corresponding %i’s. %i18 specifically shows one such example. It does laplace() of the output at %o16, giving back the expression, which was input to ilt() of %i16.

Solving differential and integral equations

Now, with these insights, we can easily solve many interesting and otherwise complex problems. One of them is solving differential equations. Let’s take a simple example of solving f'(t) + f(t) = e^t, where f(0) = 0. First we take the Laplace transform of the equation. Then substitute the value for f(0), and simplify to obtain the Laplace of f(t), i.e. F(s). And, then finally compute the inverse Laplace transform of F(s), to get the solution for f(t).

$ maxima -q
(%i1) string(laplace(diff(f(t), t) + f(t) = exp(t), t, s));
(%o1)      s*'laplace(f(t),t,s)+'laplace(f(t),t,s)-f(0) = 1/(s-1)

Substituting f(0) as 0, and simplifying we get, laplace(f(t),t,s) = 1/((s-1)*(s+1)), for which we do an inverse Laplace transform:

(%i2) string(ilt(1/((s-1)*(s+1)), s, t));
(%o2)                          %e^t/2-%e^-t/2
(%i3) quit();

Thus, giving f(t) = (e^t – e^-t) / 2, i.e. sinh(t), which definitely satisfies the given differential equation.

Similarly, we can solve equations with integrals. And, why only integrals – rather equations with both differentials and integrals. Such equations come very often in solving for electrical circuits with resistors, capacitors, and inductors. Let’s again take a simple example to demonstrate the fact. Say, we have 1 ohm resistor, 1 farad capacitor, and 1 henry inductor in series being powered by a sinusoidal voltage source of frequency w. What would be the current in the circuit, assuming it to be zero at t = 0? It would yield the following equation: R * i(t) + 1/C * ∫ i(t) dt + L * di(t)/dt = sin(w*t), where R = 1, C = 1, L =1.

So, the equation simplifies to i(t) + ∫ i(t) dt + di(t)/dt = sin(w*t). Now, following the procedure as described above, we do the following steps:

$ maxima -q
(%i1) string(laplace(i(t) + integrate(i(x), x, 0, t) + diff(i(t), t) = sin(w*t),
	t, s));
(%o1) s*'laplace(i(t),t,s)+'laplace(i(t),t,s)/s+'laplace(i(t),t,s)-i(0) = w/(w^2+s^2)

Substituting i(0) as 0, and simplifying, we get laplace(i(t), t, s) = w/((w^2+s^2)*(s+1/s+1)). Solving that by inverse Laplace transform, we very easily get the complex expression for i(t) as follows:

(%i2) string(ilt(w/((w^2+s^2)*(s+1/s+1)), s, t));
Is  w  zero or nonzero?

n; /* Our input: Non-zero frequency */
(%o2) w^2*sin(t*w)/(w^4-w^2+1)-(w^3-w)*cos(t*w)/(w^4-w^2+1)+%e^-(t/2)*
	(sin(sqrt(3)*t/2)*(-(w^3-w)/(w^4-w^2+1)-2*w/(w^4-w^2+1))/sqrt(3)+
	cos(sqrt(3)*t/2)*(w^3-w)/(w^4-w^2+1))
(%i3) quit();

Twenty-second Article >>

   Send article as PDF