Uncategorized at Samuel Jacob's Weblog

Archive for the ‘Uncategorized’ Category

I2C 20×4 LCD module and Arduino

Recently I was working on a ZigBee project using XBee. Since XBee occupied the Arduino UART port, I decided use a character LCD for debug logs. I got the SainSmart 20×4 LCD module with i2c interface. The connections are simple:

Arduino	LCD
5v	VCC
GND	GND
SDA	A5/SDA
SCL	A4/SCL

But I couldnt make it work with sample code provided, after few googling I found that the sample code has a wrong i2c address. Even after using the correct I2C address(0x3f), it didnt work, but I was getting only to horizontal black bars on the screen.

I confirmed the I2C is working by using I2C Explorer. Finally after updating the i2c library and with the following code, it started working. I found this code on a amazon review and modified for my purpose.

/* * Sample code for SainSmart IIC/I2C/TWI Serial 2004 20x4 LCD Module. * License: GPL */ #include <Wire.h> #include <LiquidCrystal_I2C.h> #define I2C_ADDR 0x3F #define En_pin 2 #define Rw_pin 1 #define Rs_pin 0 #define D4_pin 4 #define D5_pin 5 #define D6_pin 6 #define D7_pin 7 #define BACKLIGHT_PIN 3 LiquidCrystal_I2C lcd(I2C_ADDR, En_pin, Rw_pin, Rs_pin, D4_pin, D5_pin, D6_pin, D7_pin); void setup() { lcd.begin (20, 4); // Switch on the backlight lcd.setBacklightPin(BACKLIGHT_PIN, POSITIVE); lcd.setBacklight(LOW); // Position cursor and write some text lcd.home(); lcd.print("Hello World"); } void loop() { }

Written by samueldotj

September 8th, 2013 at 4:12 pm

Posted in Uncategorized

Tagged with Arduino

Fix loop in a linked list

without comments

Cycle or loop in a linked list with $n$ nodes is shown in pictorial representation.

Loop in a singly linked list

In this picture the number of nodes in the list is $n$ and the last node points to node at a position x(which created the cycle). From the picture it is obvious that to fix the loop:

Find the last element
Correct it to point end(NULL)

In the above steps, step 1(find the last element) is little difficult if total number of nodes in the list is unknown. In this post I will describe a method I discovered to find the last node. I drew couple of pictures to explain the complexity of the problem. The following pictures explains the same loop condition but in different form. It explains why it is hard to find the last node.

The illustration also tells us the following
$n = x+y$
where
$n$ is total number of nodes in the list
$x$ is number of nodes before the cycle starts.
$y$ is number of nodes forming the cycle.

If we have value of $x$ and $y$ then the equation can be solved, which will give the last node’s location.

Finding $y$

Detect the cycle using Floyd’s Cycle detection algorithm. (Two pointer with varying speed)
When cycle is detected
1. Store the current node as H
2. Move to next node and increment y(y++)
3. If current node is H then exit
4. Goto step 2

Finding $x$
Let’s first see the easiest way to solve this:

Have two pointers (p1, p2)
p1 = node 0
p2 = p1 + y nodes
if p1 == p2 then we found the result is $x = p1$
p1 = p1 + y nodes
goto step 3.

The complexity of this algorithm linear depends on $x$ . For example if $x$ is 10K and $y$ is 2 then number of node visits are > 20K. In other words the complexity is $O(2x + y)$ .

I believe it can be done in $O(n)$ or $O(x + y)$ with following method This following diagram captures state when the “tortoise and the hare” algorithm detects the cycle.

Lets define few more variables at the time of cycle detection:
$T$ is the total number of nodes tortoise traveled.
$H$ is the total number of nodes hare traveled.
$r$ can be defined as number of nodes before the ‘last node’

$T = 2H \newline x + cy - r = T \newline x + y - r = H \newline$
where c is the number of complete cycles hare covered.
$T > H \newline c > 1 \newline r >= x \ and \ r <= n \newline$
From this we can derive
$c = H / y + 1$

Using value of $c$ , $r$ can be derived.
$x + y - r = H \newline r = x + y - H \newline \newline x + cy - r = T \newline x = T - cy + r \newline \newline r = T - cy + r + y - H \newline r = H - cy + r + y \newline$

Using this formula $r$ can be found. With this $r$ value, the last node can be found by travelling $r-1$ nodes where T and H met.

Written by samueldotj

August 29th, 2013 at 3:35 pm

Posted in Uncategorized

Kernel(FreeBSD) Concurrency

without comments

Today, I had to revisit how FreeBSD system call path was synchronized. And here it is:

Kernel data structures are tradionally protected by the following synchronization methods.

Interrupt disabling
Spinlock
System priority level
Mutex

Disabling interrupts is the easiest method because only one code path can be executed with in a interrupt disbale/enable boundary. However exceptions are there which dont honour interrupts disabled attribute.

Eg:

Exceptions
Faults
NMI

Disabling interrupts wont work on SMP because interrupts can be disabled/enabled only on current CPU. Disabling interrupts is problematic if the code path takes longer time to complete. Because the kernel would have lost interrupts from devices.

Spinlocks is a datastructure residing on memory and acceissible from all the processors on the system. Before entering a critical code path spinlock is taken and all other access to that code path is prohibted and the other cpus will be in a loop trying to get the lock and enter. There are certain rules while creating a spinlock to avoid dead locks and gain performance from SMP.

Locking order heierarchy should be maintained to avoid dead locks.
Fine grained locks instead of single big lock to gain performance on SMP.

Spinlock alone would cause a dead lock in a preemptive kernel. Avoiding this in easy way is disabling interrupt because scheduler wont run. However it again would introduce a problem of losing interrupts.

system priority level or SPL is the prefered method to use with spinlock to avoid lock issues and also get interrupts from devices. SPL rules:

And all spinlocks are at greater SPL than scheduler.
All spinlocks should have a associated SPL and at that or greater SPL level only the spinlock should be taken.

Note:

In simpler term spl is equivalent to masking interrupts.
SPL is per processor, so the spinlock should have locking order hierarchy, otherwise deadlock for sure.

Mutexes used because even with fine grained spinlock there is performance penalty when other CPUs are waiting(looping) for a spinlock. Mutex solves this problem by scheduling out the looping threads in the other CPUs and selecting other threads to run.

Note:

Mutex cant be used in certain situations eg: a interrupt handler which runs without context cant take mutex because it might be put into sleep.
Combining mutex and spinlock requires only one condition – after a spinlock is taken no mutex acquire should be attempted.

FreeBSD 6.x uses mutex and spinlock – MUTEX_DEF and MUTEX_SPIN.

MUTEX_DEF – Is a mutex which result in going to sleep.

MUTEX_SPIN – Is a spinlock which never puts the caller into sleep but spins and also disables interrupts.

When FreeBSD was optimized for SMP, spinlocks were removed and mutex was introduced.

It also introduced context full interrupt handlers; now interrupt handlers can sleep, so can use mutex. Since most of the system calls was not ported to SMP, they were protected using a big mutex called Giant.

Giant – Gaint is a MUTEX_DEF which protects the code path of most system calls.

Written by samueldotj

February 10th, 2010 at 4:17 am

Posted in Uncategorized

Better build system

with one comment

I was using “make”(http://en.wikipedia.org/wiki/GNU_build_system) to build and clean my projects. The makefiles grew bigger enough to not maintainable state. Recently I came to know about waf(http://code.google.com/p/waf/) from a forum, so decided to give a try. I went through the waf documentation and it took 2 hours to understand how it works and it took 2 days to convert all my makefiles to waf wscripts and wscript_build files.

The basic problem with make was I have write rules to how to build object files from source and

then to clean I have to write how to delete the object files. With waf the problem is simplified, you have to tell what all source files and it will take care of how to compile and link. It will also take care of how to clean the project and the dependency between files are also taken care, so no need for gcc –M and dependency files etc. The feature I liked in waf is it has colored output with progress bar 🙂

The other problem solved in Ace project compilation was build configuration. Waf will configure the project for the first time, so it solved the different cross compiler required for Ace OS.

Waf(http://code.google.com/p/waf/) is really good alternative/replacement for make tools.

Written by samueldotj

March 17th, 2009 at 3:54 am

Posted in Uncategorized

Samuel Jacob's Weblog

Archive for the ‘Uncategorized’ Category

I2C 20×4 LCD module and Arduino

Fix loop in a linked list

Kernel(FreeBSD) Concurrency

Better build system

Recent Posts

Categories

Recent Comments

Meta