The Extra Space

New/Delete advantages

2008-10-01T07:08:00.000-07:00

Brushing through some basics:

new/delete invokes constructor/destructor. Malloc/free will not.
new does not need typcasting. Malloc requires typcasting the returned pointer.
new/delete operators can be overloaded, malloc/free can not.
new does not require you to explicitly calculate the quantity of memory required. (Unlike malloc)

Ref: C / C++ and Dynamic memory allocation

Colour your Eclipse Chrome!

2008-09-15T18:59:00.000-07:00

To add a browser to eclipse, Go to Window -> Preferences -> General -> Web
Browser and click Add.

To find the location of your chrome installation, try using the Properties of
the Shortcut Link. [Right-Click on Short-Cut -> Properties -> Target]

More chrome command-line options.

Make sure you have the Chrome browser checked to act as your default Eclipse Browser.

Setting SVN with HTTP(S) - It's Simple

2008-09-12T08:50:00.001-07:00

I was looking into SVN and it was a great experience setting it up.

svn create --fs-type fsfs <repos-path>

NOTE: Why FSFS is used ?

HOMEWORK before start!!! - For creating new Products and maintain the tags,branches and truck please refer Strategies for Repository Deployment

Taking Backup

Create Dump File
$ svnadmin dump <repos-path> > <dumpfile>
Import Backup Dump File
$ svnadmin load <repos-path> < <dumpfile>

Access Protocol: Suggested is HTTPS

Disable svn
- Make sure the svnserve is not running as deamon or inetd process.
  OR
- Disable read and write through svnserve - Edit the svnserve.conf and set anon-access=none and auth-access = none
Basic Setup
- Load Access Modules in httpd.conf
  LoadModule dav_module modules/mod_dav.so
  LoadModule dav_svn_module modules/mod_dav_svn.so
  <Location /repos>
  DAV svn
  SVNPath /absolute/path/to/repository
  </Location>
- Make sure that the repository has read-write permissions for apache
  chown -R apache <repos-path>
- Restart server & check
User Authentication
- Create a htpasswd file with users
  - $ htpasswd -c /path/to/htpasswd/file user - Create User Credential
  - $ htpasswd /path/to/htpasswd/file user - Append Users to List
  - $ htpasswd -b /path/to/htpasswd/file user password - Batch mode, password is visible
- Add the below to httpd.conf under the SVN Location
AuthType Basic
AuthName "Subversion repository"
AuthUserFile /path/to/htpasswd/file
# only authenticated users may access the repository
Require valid-user
- Restart and check
NOTE: There is no need to restart server when the htpasswd file changes
Per-Directory Access Control
- Create an Access control Policy File
  [groups]
  Full-SVN-RO = svnreader
  Proj1-RW = user1 user2 user3
  Proj1-RO = user4
  Proj2-RW = user1 user6 user7
  Proj2-RO = user8 user2
  EveryOne = @Full-SVN-RO, @Proj1-RW, @Proj1-RO, @Proj2-RW, @Proj2-Ro
  
  # Access control to whole SVN
  [/]
  svnadmin = rw # No Groups allowed to Read-Write the whole SVN Repos
  @Full-SVN-RO = are
  
  # Access to Proj1
  [/Proj1]
  @Proj1-RW = rw
  @Proj1-RO = r
  
  # Access to Proj2
  [/Proj2]
  @Proj2-RW = rw
  @Proj2-RO = r
- Add the below module to httpd.conf
  LoadModule authz_svn_module modules/mod_authz_svn.so
- Add Access control Policy File in Location of SVN
  AuthzSVNAccessFile /path/to/access/file
- Restart httpd and check
NOTE: There is no need to restart server when the Access control Policy File changes
Enable SSL
- Setup Apache with SSL.
- Redirect Request to HTTPS
  #Redirect all port 80 requests to 443
  RewriteEngine On
  RewriteCond %{SERVER_PORT} !^443$
  RewriteRule ^/(.*) https://%{SERVER_NAME}/$1 [L,R]
- Deny if not accessed without SSL. Add the below under the Location of SVN
  SSLRequireSSL
- Restart and check
Apache logging
CustomLog logs/svn_logfile "%t %u %{SVN-ACTION}e" env=SVN-ACTION

Single Repository vs. Multiple Repository
I feel Single Repositories are easy to maintain and administer. Only if there are hundred's of project then I suggest Multiple Repositories.

An example of httpd.conf for multiple repositories.

<Location /svn/>
DAV svn
SVNParentPath /data/subv/repos/
</Location>

<Location /svn/testA/>
# Authenticate a user
AuthType Basic
AuthName "TestA Subversion Repository"
AuthUserFile /data/subv-testA/perms/users
Require valid-user
# Authenticate permissions
AuthzSVNAccessFile /data/subv-testA/perms/perms
# Requires SSL
SSLRequireSSL
</Location>

<Location /svn/testB/>
# Authenticate a user
AuthType Basic
AuthName "TestB Subversion Repository"
AuthUserFile /data/subv-testB/perms/users
Require valid-user
# No permissions
# AuthzSVNAccessFile /data/subv-testB/perms/perms
# No SSL
# SSLRequireSSL
</Location>

Kernel Locking Techniques

2008-09-04T05:16:00.001-07:00

link: http://www.linuxjournal.com/node/5833/

With the rise of multi-threaded and multi-process programming, the race condition in many code is becoming evident.

Race Condition
A race hazard (or race condition) is a flaw in a system or process where the output exhibits unexpected critical dependence on the relative timing of events. The term originates with the idea of two signals racing each other to influence the output first.
en.wikipedia.org/wiki/Race_condition

This can be solved by using atomic operations or some locking semantics. Getting to understand which shared data is to locked or made atomic, does an interrupt disturb the locking semantics is tough. If the locking semantics are wrongly designed -- deadend, called deadlock.

Deadlock
In operating systems, a situation in which two or more processes are blocked while waiting for resources that the other controls so that none of the affected processes can continue to execute. Also known as the "deadly embrace."
www.ssuet.edu.pk/taimoor/books/0-7897-1063-3/appa.htm

The linux Kernel provides some functions to reduce data races

Why Do We Need Locking in the Kernel?
Thus the issue here is "relative timing of events" or a synchronization problem. Shared memory, though with it many advantages poses many design issues. A simple i++ (i=2) done by 2 processes will result in an unexpected result 3, when it should have been 4 (increment twice). These critical regions require locking. The Linux kernel provides a family of locking primitives that developers can use to write safe and efficient code.

Critical regions
A critical section is a piece of code that can only be executed by one process at a time. It will usually terminate in fixed time and a process will only have to wait a fixed time to enter it. Some synchronisation mechanism is required at the entry and exit of the critical section to ensure exclusive use, for example a semaphore.
en.wikipedia.org/wiki/Critical_section

Why is SMP Locks in a Uniprocessor Kernel?
Though you may not have a SMP machine when you write code, others who are using your code may. And the linux maintaners, will never insert any code that does not handle locking issues. SMP and UP kernels are distinct. "This allows certain locks not to exist at all in a UP kernel. Different combinations of CONFIG_SMP and CONFIG_PREEMPT compile in varying lock support. It does not matter, however, to the developer: lock everything appropriately and all situations will be covered."

Atomic Operators
Atomic Operations are the simplest ways of achieving kernel synchronization. The other locking primitives are built using Atomic operations.

Atomic Operation
An operation that cannot be interrupted docs.cray.com/books/004-2518-002/html-004-2518-002/zglossaryqkdxjklv.html

Operation that executes without interference by other concurrently-executing processes or threads. www.cise.ufl.edu/research/ParallelPatterns/PatternLanguage/Background/Glossary.htm

Consider the previous example of i++. If we could read i, increment it and write it back to memory in one uninterruptible operation, the race condition discussed above would not be an issue. Atomic operators provide these uninterruptible operations.

atomic_t v;
atomic_set(&v, 5);  /* v = 5 (atomically) */
atomic_add(3, &v);  /* v = v + 3 (atomically) */
atomic_dec(&v);     /* v = v - 1 (atomically) */
printf("This will print 7: %d\n", atomic_read(&v));

Some points to remember.

you cannot pass an atomic_t to anything but one of the atomic operators.
you cannot pass anything to an atomic operator except an atomic_t.

Spinlocks
When more complex locking design is needed, we don't rely on atomic operations. Spinlocks are commonly used in the kernel, defined in include/asm/spinlock.h and include/linux/spinlock.h. The spinlock is a very simple single-holder lock. If a process attempts to acquire a spinlock and it is unavailable, the process will keep trying (spinning) until it can acquire the lock. This simplicity creates a small and fast lock. The basic use of the spinlock is:

spinlock_t mr_lock = SPIN_LOCK_UNLOCKED;
unsigned long flags;
spin_lock_irqsave(&mr_lock, flags);
/* critical section ... */
spin_unlock_irqrestore(&mr_lock, flags);spin_lock_irqsave() will disable interrupts locally and provide the spinlock on SMP. This covers both interrupt and SMP concurrency issues
spin_unlock_irqrestore(), interrupts are restored to the state when the lock was acquired.

With a UP kernel, the above code compiles to the same as:

unsigned long flags; save_flags(flags); cli(); /* critical section ... */ restore_flags(flags);spin_lock_irq() disables and re-enables interrupts unconditionally, in the same manner as cli() and sti(). Use this only when you know that interrupts were not already disabled before the acquisition of the lock.
spinlock_t mr_lock = SPIN_LOCK_UNLOCKED; spin_lock_irq(&mr_lock); /* critical section ... */ spin_unlock_irq(&mr_lock);

spin_lock() and spin_unlock() methods that acquire and release the specified lock without any interaction with interrupts.
spin_lock_bh() that implements the standard spinlock as well as disables softirqs. This is needed when you have code outside a softirq that is also used inside a softirq. The corresponding unlock function is naturally spin_unlock_bh().

You must be careful not to re-acquire a spinlock you already hold, or you will deadlock.

Spinlocks should be used to lock data in situations where the lock is not held for a long time--recall that a waiting process will spin, doing nothing, waiting for the lock. (See the ``Rules'' Sidebar for guidelines on what is considered a long time.) Thankfully, spinlocks can be used anywhere. You cannot, however, do anything that will sleep while holding a spinlock. For example, never call any function that touches user memory, kmalloc() with the GFP_KERNEL flag, any semaphore functions or any of the schedule functions while holding a spinlock. You have been warned.

Semaphores
If you need a lock that is safe to hold for longer periods of time, safe to sleep with or capable of allowing concurrency to do more than one process at a time, Linux provides the semaphore. Semaphores in Linux are sleeping locks. Because they cause a task to sleep on contention, instead of spin, they are used in situations where the lock-held time may be long. Conversely, since they have the overhead of putting a task to sleep and subsequently waking it up, they should not be used where the lock-held time is short.
Semaphores are represented by a structure, struct semaphore, which is defined in include/asm/semaphore.h. The structure contains a pointer to a wait queue and a usage count. The wait queue is a list of processes blocking on the semaphore. The usage count is the number of concurrently allowed holders. If it is negative, the semaphore is unavailable and the absolute value of the usage count is the number of processes blocked on the wait queue. The usage count is initialized at runtime via sema_init(), typically to 1 (in which case the semaphore is called a mutex).
Semaphores are manipulated via two methods: down (historically P) and up (historically V). The former attempts to acquire the semaphore and blocks if it fails. The later releases the semaphore, waking up any tasks blocked along the way.
Semaphore use is simple in Linux. To attempt to acquire a semaphore, call the down_interruptible() function. This function decrements the usage count of the semaphore. If the new value is less than zero, the calling process is added to the wait queue and blocked. If the new value is zero or greater, the process obtains the semaphore and the call returns 0. If a signal is received while blocking, the call returns -EINTR and the semaphore is not acquired.
The up() function, used to release a semaphore, increments the usage count. If the new value is greater than or equal to zero, one or more tasks on the wait queue will be woken up:

struct semaphore mr_sem; sema_init(&mr_sem, 1); /* usage count is 1 */ if (down_interruptible(&mr_sem)) /* semaphore not acquired; received a signal ... */ /* critical region (semaphore acquired) ... */ up(&mr_sem);

down() function, which differs in that it puts the calling task into an uninterruptible sleep. A signal received by a process blocked in uninterruptible sleep is ignored
down_trylock() function, which attempts to acquire the given semaphore. If the call fails, down_trylock() will return nonzero instead of blocking.

Reader/Writer Locks
Since it is typically safe for multiple threads to read data concurrently, so long as nothing modifies the data, reader/writer locks allow multiple concurrent readers but only a single writer (with no concurrent readers). If your data access naturally divides into clear reading and writing patterns, especially with a greater amount of reading than writing, the reader/writer locks are often preferred. The reader/writer spinlock is called an rwlock and is used similarly to the standard spinlock, with the exception of separate reader/writer locking:

rwlock_t mr_rwlock = RW_LOCK_UNLOCKED; read_lock(&mr_rwlock); /* critical section (read only) ... */ read_unlock(&mr_rwlock); write_lock(&mr_rwlock); /* critical section (read and write) ... */ write_unlock(&mr_rwlock);

Likewise, the reader/writer semaphore is called an rw_semaphore and use is identical to the standard semaphore, plus the explicit reader/writer locking:

struct rw_semaphore mr_rwsem; init_rwsem(&mr_rwsem); down_read(&mr_rwsem); /* critical region (read only) ... */ up_read(&mr_rwsem); down_write(&mr_rwsem); /* critical region (read and write) ... */ up_write(&mr_rwsem);Use of reader/writer locks, where appropriate, is an appreciable optimization.
Note: reader locks cannot be automatically upgraded to the writer variant. Therefore, attempting to acquire exclusive access while holding reader access will deadlock.

Big-Reader Locks
Big-reader locks (brlocks), defined in include/linux/brlock.h, are a specialized form of reader/writer locks. It is a spinning lock that is very fast to acquire for reading but incredibly slow to acquire for writing. Therefore, they are ideal in situations where there are many readers and few writers. While the behavior of brlocks is different from that of rwlocks, their usage is identical with the lone exception that brlocks are predefined in brlock_indices (see brlock.h):

br_read_lock(BR_MR_LOCK); /* critical region (read only) ... */ br_read_unlock(BR_MR_LOCK);

The Big Kernel Lock
Linux contains a global kernel lock, kernel_flag, that was originally introduced in kernel 2.0 as the only SMP lock. During 2.2 and 2.4, much work went into removing the global lock from the kernel and replacing it with finer-grained localized locks. Today, the global lock's use is minimal. It still exists, however, and developers need to be aware of it.
The global kernel lock is called the big kernel lock or BKL. It is a spinning lock that is recursive; therefore two consecutive requests for it will not deadlock the process (as they would for a spinlock). Further, a process can sleep and even enter the scheduler while holding the BKL. When a process holding the BKL enters the scheduler, the lock is dropped so other processes can obtain it. This is also known as release-on-block/sleep These attributes of the BKL helped ease the introduction of SMP during the 2.0 kernel series. Today, however, they should provide plenty of reason not to use the lock.
Use of the big kernel lock is simple. Call lock_kernel() to acquire the lock and unlock_kernel() to release it. The routine kernel_locked() will return nonzero if the lock is held, zero if not. For example:

lock_kernel(); /* critical region ... */ unlock_kernel();

Recovering Grub

2008-09-04T05:15:00.001-07:00

I happened to reinstall Win XP on my DebianLinux+WinXP machine and my MBR was overwritten by re-installation.

I loaded Ubuntu Live CD:

mounted the root parition
chroot to the mount-point
grub-install /dev/hda

That is it... grub was up and running.

Licenses: Derived Works

2008-05-22T01:41:00.001-07:00

After reading the GPL & Libraries, for the first understood more about the definition derived works.

It is not only adding more functionality to a particular open-source code, but also if it is used in combination with another application in the form of libraries ( static and dynamic ).

Then almost all program linking with libc will have to GPL'ed. To avoid this we have LGPL. All system libraries are LGPL, where derived works are not necessarily LGPL'ed.

Further Reading:
http://www.onlamp.com/pub/a/onlamp/2004/11/18/licenses.html
http://www.linuxjournal.com/article/6366

Indent

2008-04-28T01:15:00.000-07:00

Content
=======
        1 Purpose:
        2 Psychological Factors:
                2.1 Pattern Recognition
                2.2 Switching between context/controls
                2.3 Eye movement
                2.4 Looking ahead
                2.5 Looking back
                2.6 Be consistent
                2.7 There's no one true style
        3. Techniques
                3.1 Spacing the Code
                        3.1.1 Horizontal Spacing
                        3.1.2 Vertical Spacing
                3.2 Grouping with Brace
                3.3 Positioning the Code Blocks
        4. Examples:
        5. Profile File
        6 References:

1 Purpose:
==========
        The prime purpose to convey the structure of the program to human readers in better and clear form.
        This is to help in better productivity, quality, maintainability and understandability

2 Psychological Factors:
========================

2.1 Pattern Recognition
-----------------------
        We survive in this world not by recognizing complete situations, nor by analyzing each situation from scratch, but by fitting the world into established recognizable patterns. For example in programming, the following represents traversing a list:
        while ( pTemp != NULL )
        {
                // Some Statements
                pTemp = pTemp->next;
        }

        Once patterns are in place it is very easy to **Filter** or **Search** for a pattern.

2.2 Switching between context/controls
--------------------------------------
        When you are talking about something, and get interrupted (and parentheses in a sentence like this is just such an example) then what you were thinking about before the interruption goes onto a 'mind stack'. Successive interruptions cause the previous context to be pushed onto the stack, and popped off again only when the interruption is completed.
        Similarly in the programming world, the code is split into contexts and controls. Usually the contexts are split using the braces and indentation.

2.3 Eye movement
----------------
        When you are reading, your eyes move from left to right and top to bottom
(unless, of course, you are Arabic or Chinese!). However, when you are reading fast, or scanning for a particular item (such as looking for a particular variable in a code procedure), the eyes skip, and prefer to move in a downwards direction only.
        Lesser the characters on the line, the more faster we read.

2.4 Looking ahead
-----------------
        When we drive we look well ahead, so we can be ready for any hazard. Similarly, as we are reading, we tend to peek ahead to absorb the context ahead of the current reading point. If it is laid out nicely, and everything looks familiar, then we relax and read comfortably at our own rate. If, however, the text ahead looks dense or unfamiliar, we tense up and start to think negatively. We are more likely to misunderstand and make mistakes if things look difficult and we are expecting to err.
        Thus, with the use of a consistent programming style, the reader is comforted simply by the 'look' of the code and can relax and concentrate on the current fragment.

2.5 Looking back
----------------
        When we reading something, particularly for the first time, and especially if we are trying to understand or learn it, we don't just read it once. We continually skip back and re-read chunks, particularly the difficult bits. There are flags in the written language to allow us to find the start of chunks, even when looking backwards. The capital at the start of a sentence helps. Splitting the text into paragraphs, with the first word indented, help too.
        The programming equivalent is to make the start of the statement group, block or function easier to find, by using white space, braces or comment blocks.

2.6 Be consistent
-----------------
        Changing the way things are done is a certain way to cause confusion in the reader, and could lead to serious error. When a style is chosen, it must be used consistently.
        The consistency principle applies to all elements of style, including naming, commenting, layout and usage. It should also be applied to the selection of standards. If, for example, one brace style is selected, then the same style should be used for both code blocks and declarations (including struct's, union's and enum's).

2.7 There's no one true style
-----------------------------
        There is no such thing as a 'correct' style. There are almost as many styles as there are programmers. Some are more sensible than others, but there is no one style that can be clearly agreed upon as being the best style to use.
        But in the end, one style must be chosen. You have to say, "This is the style that we will use. We have argued over which one to use, and the consensus is that this is it". Doubters and dissenters may have to be persuaded or coerced, for although your style is not perfect, it has been chosen to be standard.
        A maintenance note: If you happen to be changing a program that does not use your style, then the professional approach is to use the style that the program uses, rather than to use your normal style. Maintaining poor style is difficult enough - maintaining several styles at once is hell!

3. Techniques
=============

3.1 Spacing the Code
--------------------
3.1.1 Horizontal Spacing
        Spacing the code increases readability by identifying the tokens in the statement. However, using more space cost you the horizontal line. A simple rule could be used:
        a. No space with object reference. Eg: pObj->member, Obj.member
        b. No spaces between unary operators and their operands. Eg: *ptr, ++i, -num
        c. All other binary operators have an equal number of spaces either side.

Indent Options:
        a. Put a space between sizeof and its argument. --blank-before-sizeof
        b. Put a space after a cast operator. --space-after-cast
        c. Insert a space between the name of the procedure being called and the
`('. --space-after-procedure-calls
        d. Put a space after every '(' and before every ')'.
--space-after-parentheses
        e. Put a space after each for. --space-after-for
        f. Put a space after each if. --space-after-if
        g. Put a space after each while. --space-after-while
        h. On one-line for and while statments, force a blank before the semicolon.
--space-special-semicolon

3.1.2 Vertical Spacing
        One means of providing a context is grouping similar statements together and differentiating between groups by a new lines:

Indent Options:
        a. Split the declarations and code. Force blank lines after the declarations. --blank-lines-after-declarations
        b. Force blank lines after procedure bodies. --blank-lines-after-procedures
        c. Force blank lines before block comments. Usually block comments are use for a sequence of statements performing a particular task.
--blank-lines-before-block-comments
        d. When compared to
                int nLenSentence, nI;                and
                int        nLenSentence,
                        nI;
                In the former, it is easier to search for "nI". Force newline after comma in declaration. --blank-lines-after-commas

3.2 Grouping with Brace
-----------------------
        Besides Vertical Spacing, another means of grouping is using Code Body Block, after branching controls.

Indent Options:
        a. Put braces on line after if, etc. --braces-after-if-line
        b. Put braces on the line after struct declaration lines.
--braces-after-struct-decl-line
        c. Group the while in do-while with the close brace. --dont-cuddle-do-while
        d. don't group the brace with else. --dont-cuddle-else
        e. For block comments, it easier to identy comments when the begin with a star. Put the ‘*’ character at the left of comments. --start-left-side-of-comments

3.3 Positioning the Code Blocks
-------------------------------
        Indentation is one major tools to define structural and control code blocks. Positioning of the braces also helps in maintaining the start and end of the code blocks.

Indent Options:
        a. Zeroth law, use tabs instead of spaces. None is interested to key in 4 spaces when compared to a tab. --use-tabs
        b. Usually a tab is considered to be 8 spaces, this will waste a lot of line space, hence specify the tab size to 4. --tab-size4
        c. Each level/hierarchy should be indented by 4 again. Set indentation level to 4 spaces. --indent-level4
        d. Put comments to the right of code in column 41. --comment-indentation41
        e. By default the case body brace is put 2 characters after the case. Indent braces after a case label 0 spaces. --case-brace-indentation0
        f. Put comments to the right of the declarations in column 41.
--declaration-comment-column41
        g. It is important to know that comment has ended, which can be identified by using the comment delimiter on a new line. Put comment delimiters on blank lines. --comment-delimiters-on-blank-lines
        h. Set maximum size of a single line to 80 characters. --line-length80
        i. The above sets the line size for a non-comment line. Set maximum size of a single comment line to 80 characters. --comment-line-length80
        j. Best place to break a long line would be binary operator. Prefer to break long lines before boolean operators. --break-before-boolean-operator
        k. When a huge line is broken (which does not contain a parenthesis), then align the next line by an offset of 4 spaces. --continuation-indentation4
        l. When a huge line is broken (which does contain a parenthesis), then align with open parenthesis. --continue-at-parentheses
        m. If you use the `-bl' option, you must specify the `-bli' option. This option specifies the number of spaces by which braces are indented. `-bli2', the default, gives the result below:
                        if (x > 0)
                         {
                                x--;
                         }

                `-bli0' results in the following:
                        if (x > 0)
                        {
                                x--;
                        }
                Indent braces 0 spaces, --brace-indent0
        n. Case label indent of 4 spaces. --case-indentation4
        o. Similarly, the brace for case should also be 0 indented. Indent braces after a case label 0 spaces. --case-brace-indentation0
        p. Similarly, the brace for struct should also be 0 indented. Indent braces of a struct, union or enum 0 spaces. --struct-brace-indentation0

3.4 Changing some Default Settings of indent
        a. By default GNU Style is used for functions --dont-break-procedure-type
        b. To format all the comments use --format-all-comments and
--format-first-column-comments

4. Examples:
============
$ indent --blank-before-sizeof
INPUT:
sizeof(int);

OUTPUT:
sizeof (int);

******************************
$ indent --space-after-cast
INPUT:
(int)'a';

OUTPUT:
(int) 'a';

******************************
$ indent --space-after-procedure-calls
INPUT:
foo(10);

OUTPUT:
foo (10);

******************************
$ indent --space-after-parentheses
INPUT:
(a+b)*c*((x-y)*(x-y));

OUTPUT:
( a + b ) * c * ( ( x - y ) * ( x - y ) );

******************************
$ indent --space-after-for
INPUT:
for(;;);

OUTPUT:
for (;;);

******************************
$ indent --space-after-if
INPUT:
if(1);

OUTPUT:
if (1);

******************************
$ indent --space-after-while
INPUT:
while(0);

OUTPUT:
while (0);

******************************
$ indent --space-special-semicolon
INPUT:
for(initial_state;loopig_condition;increment);
while(looping_condition);

OUTPUT:
for (initial_state; loopig_condition; increment) ;
while (looping_condition) ;

******************************
$ indent --blank-lines-after-declarations
INPUT:
int a = 10;
int b = 20;
int c;
c = a + b;

OUTPUT:
int a = 10;
int b = 20;
int c;

c = a + b;

******************************
$ indent --blank-lines-after-procedures
INPUT:
void foo ( )
{
        /* Do Something */
}
void bar ( )
{
        /* Do yet another thing */
}

OUTPUT:
void
foo ()
{
/* Do Something */
}

void
bar ()
{
/* Do yet another thing */
}

******************************
$ indent --blank-lines-before-block-comments
INPUT:
end_of_sequence_statements_performing_task_A;
/*
* Task B
*
* Some Alogorithms is mentioned
* Step 1: Blah
* Step 2: Blah Blah
* Step 3: More Blahs
*/
step_1;
step_2;
step_3;

OUTPUT:
end_of_sequence_statements_performing_task_A;

/*
* Task B
*
* Some Alogorithms is mentioned
* Step 1: Blah
* Step 2: Blah Blah
* Step 3: More Blahs
*/
step_1;
step_2;
step_3;

******************************
$ indent --blank-lines-after-commas
INPUT:
int nLenSentence = 0, nI;

OUTPUT:
int nLenSentence = 0,
nI;

******************************
$ indent --braces-after-if-line
INPUT:
if ( condition ) {
        some_statement;
}

OUTPUT:
if (condition)
{
some_statement;
}

******************************
$ indent --braces-after-struct-decl-line
INPUT:
struct someStruct {
        int int_member;
        char char_member;
};

OUTPUT:
struct someStruct
{
int int_member;
char char_member;
};

******************************
$ indent --dont-cuddle-do-while
INPUT:
do
{
        body_of_loop;
        increment;
} while ( looping_condition );

OUTPUT:
do
{
body_of_loop;
increment;
}
while (looping_condition);

******************************
$ indent --dont-cuddle-else
INPUT:
if ( cond )
{
        do_something;
} else
{
        do_nothing;
}

OUTPUT:
if (cond)
{
do_something;
}
else
{
do_nothing;
}

******************************
$ indent --comment-indentation41
INPUT:
sum=operaand1+operand2;        /* Adds two operands */

OUTPUT:
sum = operaand1 + operand2;                                /* Adds two operands */

******************************
$ indent --case-brace-indentation0
INPUT:
switch ( value )
{
case const1:
                {
                        do_something;
                }
                break;
}

OUTPUT:
switch (value)
{
case const1:
{
do_something;
}
break;
}

******************************
$ indent --declaration-comment-column41
INPUT:
int nLenWord = 0;        /* No of characters in word */

OUTPUT:
int nLenWord = 0;                                                /* No of characters in word */

******************************
$ indent --line-length80
INPUT:
if ( ( ( date.year % 4 ) == 0 && ( date.year % 100 ) != 0 ) && date.month == 2 && date.day == 29 )
{
        do_some_valid_operation;
}

OUTPUT:
if (((date.year % 4) == 0 && (date.year % 100) != 0) && date.month == 2
&& date.day == 29)
{
do_some_valid_operation;
}

******************************
$ indent --line-length80 --break-before-boolean-operator --continuation-indentation4
INPUT:
bValidDay = ( ( date.year % 4 ) == 0 && ( date.year % 100 ) != 0 ) && date.month == 2 && date.day == 29 ;

OUTPUT:
bValidDay = ((date.year % 4) == 0 && (date.year % 100) != 0) && date.month == 2
&& date.day == 29;

******************************
$ indent --line-length80 --break-before-boolean-operator --continuation-indentation4 --continue-at-parentheses
INPUT:
bValidDay = ( ( ( ( date.year % 4 ) == 0 ) && ( ( date.year % 100 ) != 0 ) ) && ( date.month == 2 ) && ( date.day == 29 ) );

OUTPUT:
bValidDay = ((((date.year % 4) == 0) && ((date.year % 100) != 0))
                 && (date.month == 2) && (date.day == 29));

******************************
$ indent --braces-after-if-line --brace-indent0
INPUT:
if ( cond ) {
        do_something;
}

OUTPUT:
if (cond)
{
do_something;
}

******************************
$ indent --braces-after-struct-decl-line --struct-brace-indentation0I
INPUT:
struct someStruct {
        int a;
        char b;
};

OUTPUT:
struct someStruct
{
int a;
char b;
};

******************************

5. Profile File
===============
        If you find that you often use indent with the same options, you may put those options into a file named ‘.indent.pro’. indent will look for a profile file in three places. First it will check the environment variable INDENT_PROFILE. If that exists its value is expected to name the file that is to be used. If the environment variable does not exist, indent looks for ‘.indent.pro’ in the current directory and use that if found. Finally indent will search your home directory for ‘.indent.pro’ and use that file if it is found. This behaviour is different from that of other versions of indent, which load both files if they both exist.

        The format of ‘.indent.pro’ is simply a list of options, just as they would appear on the command line, separated by white space (tabs, spaces, and newlines). Options in ‘.indent.pro’ may be surrounded by C or C++ comments, in which case they are ignored.

********** COPY THE BELOW IN .indent.pro file
--blank-before-sizeof
--space-after-cast
--space-after-procedure-calls
--space-after-parentheses
--space-after-for
--space-after-if
--space-after-while
--space-special-semicolon

--blank-lines-after-declarations
--blank-lines-after-procedures
--blank-lines-before-block-comments
--blank-lines-after-commas

--braces-after-if-line
--braces-after-struct-decl-line
--dont-cuddle-do-while
--dont-cuddle-else
--start-left-side-of-comments

--use-tabs
--tab-size4
--indent-level4
--comment-indentation41
--case-brace-indentation0
--declaration-comment-column41
--comment-delimiters-on-blank-lines
--line-length80
--comment-line-length80
--break-before-boolean-operator
--continuation-indentation4
--continue-at-parentheses
--brace-indent0
--case-indentation4
--case-brace-indentation0
--struct-brace-indentation0

--dont-break-procedure-type
--format-all-comments
--format-first-column-comments
************* COPY TILL THE ABOVE LINE TO .indent.pro

6 References:
=============
        a. C Style: Standards and Guidelines        -        http://syque.com/cstyle/
        b. Indent Style (Wikipedia)        -        http://en.wikipedia.org/wiki/Indent_style
        c. Indent Man Pages        -        http://www.linuxmanpages.com/man1/indent.1.php

This document is licensed under the Creative
Commons Attribution 3.0 Unported License (
http://creativecommons.org/licenses/by/3.0/ )

Starting Brew from Scratch from Visual Studio 2005 Express Edition

2008-04-28T00:37:00.000-07:00

Contents:
=========
        1. Install Brew SDK
        2. Generate MIF
        3. Create a skeleton project
        4. Important Notes

1. Install Brew SDK
===================
        a. Download an Install the Brew SDK, preferably 2.1.0. For Documentation reference 3.x SDK could be used.
        b. To keep all the project file, mfx files machine independent, create an Environment Variable BREWSDK210EN pointing to the BREW SDK Directory. Please use DOS File formats in Environment variable. ( For 3.1.2 SDK use BREWSDK312EN, for a 2.0.1 Japanese SDK use BREWSDK201JP)
                eg: Assuming the BREW SDK is installed in "F:\Program Files\BREW SDK v2.1.0" to get the DOS format use DIR /X /AD command.
************************************
F:\>dir /x /ad
Volume in drive C has no label.
Volume Serial Number is 8CC3-3122
04/14/2008 04:11 PM <DIR> PROGRA~1 Program Files
04/17/2008 10:57 AM <DIR> WINDOWS
************************************
The DOS file format of Program Files is PROGRA~1

************************************
F:\Program Files>dir /x /ad
Volume in drive C has no label.
04/17/2007 08:22 PM <DIR> BREW31~1.2 BREW 3.1.2
04/19/2007 05:57 PM <DIR> BREW31~1.3 BREW 3.1.3
04/19/2007 06:28 PM <DIR> BREW31~1.4 BREW 3.1.4
10/29/2007 04:43 PM <DIR> BREW31~1.5 BREW 3.1.5
07/24/2007 04:13 PM <DIR> BREWBR~1.0 BREW Browser v2.0.0
04/17/2007 08:43 PM <DIR> BREWSD~1.1 BREW SDK Tools 1.0.1
08/09/2007 03:25 PM <DIR> BREWSD~3.1 BREW SDK Tools 1.1.1
10/04/2007 01:04 AM <DIR> BREWSD~1.1SP BREW SDK Tools 1.1.1 SP01
01/21/2008 01:22 PM <DIR> BREWSD~2.1 BREW SDK v2.0.1
04/27/2007 02:48 PM <DIR> BREWSD~1.0 BREW SDK v2.1.0
04/19/2007 05:40 PM <DIR> BREWSD~1.3 BREW SDK v2.1.3
07/26/2007 12:33 AM <DIR> BREWUI~1 BREW UI Widgets
*******************************
The DOS file format for BREW SDK v2.1.0 is BREWSD~1.0 (**Note: This is system dependent**)

So the path to the BREW SDK is F:\PROGRA~1\BREWSD~1.0\

To add Environment Variable
        1. Right-Click "My Computer"
        2. Properties->Advanced->Environment Variable
        3. Click "New" under the "System Variable" Section
        4. Add Variable Name as BREWSDK210EN
        5. Add Variable Value as F:\PROGRA~1\BREWSD~1.0\

2. Generate MIF
===============
        a. Open MIF Editor, listed under BREW SDK Tools
        b. In the BREW MIF Editor window, click the Applets tab.
        c. Create a new applet, by clicking the New Button in the List of Applets defined in this Module. The "Specify BREW Class ID" Windows pops.
        d. Select the Locally Radio Button.
        e. Add a unique Class ID (say "0x12345678", ( you should create new class id's every time you create a new project ).
        f. Also put the put the Class Name (say "FIRSTHELLOWORLD")
        g. Click Ok, you will be prompted to generate file. Save the BID file in the Project Directory. ( FIRSTHELLOWORLD.bid )
        h. For 2.1.0, add the Images from the "images" Directory
                * Large                ->        BrewImage-1.bmp
                * Medium        ->        BrewIcon-1.bmp
                * Small                ->        Games16x16-1.bmp
        i. Now Save the file in the project directory. ( firsthelloworld.mfx )
        j. To make the MFX machine independent use relative path.
                * I have created a copy of firsthelloworld.mfx created in Step 2.i as
                firsthelloworld.mfx.start
                * Now edit the firsthelloworld.mfx in Notepad (any Text
                Editor), find the below
**************
        <Object Id="21" Name="IDI_OBJECT_21">
                <File>F:\temp\firsthelloworld\images\BrewIcon-1.bmp</File>
        </Object>
        <Object Id="22" Name="IDI_OBJECT_22">
                <File>F:\temp\CVS_Work\firsthelloworld\images\BrewImage-1.bmp</File>
        </Object>
        <Object Id="23" Name="IDI_OBJECT_23">
                <File>F:\temp\CVS_Work\firsthelloworld\images\Games16x16-1.bmp</File>
        </Object>
*************
When MFX is compiled in another system, the project directory could be anything but E:\Work\CVS_Work\firsthelloworld, so use relative path ".". Dot (.) stands for Current Directory.
**************
        <Object Id="21" Name="IDI_OBJECT_21">
                <File>.\images\BrewIcon-1.bmp</File>
        </Object>
        <Object Id="22" Name="IDI_OBJECT_22">
                <File>.\images\BrewImage-1.bmp</File>
        </Object>
        <Object Id="23" Name="IDI_OBJECT_23">
                <File>.\images\Games16x16-1.bmp</File>
        </Object>
*************

Now open this edited MFX file and Compile. ( Output firsthelloworld.mif ).

One inconveneice with MIF Editor is any time you edit the MFX file, it will replace the Relative Path with Actual Path, so everytime you "save" the file, edit with with a notepad after saving.

3. Creating a Skeleton Project
==============================
3.1 New Project
---------------
        a. Open Visual Studio 2005 Express Edition
        b. Create a New Project
        c. Choose Project Type as Win32
        d. Choose Template as Windows Console Application
        e. Name: firsthelloworld
        f. Location: As your preference
        g. Unselect "Create directory for solution"
        h. OK -> Next
        i. Select "Empty Project"
        j. Unselect "Precompiled header"
        k. Finished

Now the Solution Explorer Pane Contains:
        firsthelloworld
                * Header Files
                * Resource Files
                * Source Files

3.2 Adding Files
----------------
        a. Right-Click on firsthelloworld project, Add -> Existing Items
        b. Add AeeAppGen.c and AeeModGen.c in the src folder of BREWSDK directory.

3.3 Setting Up a Brew Application
        a. Right-Click on firsthelloworld project, Properties
        b. Make sure the Configuration Name is Active(Debug)
        c. On the Left Pane, Configuration Properties -> General
                * Set Configuration Type = Dynamic Library (.dll)
        d. Configuration Properties -> Linker -> General
                * Set OutputFile = $(OutDir)\$(ProjectName).dll
        e. Configuration Properties -> C/C++ -> Preprocessor
                * Preprocessor = WIN32;_DEBUG;_WINDOWS;_USRDLL;AEE_SIMULATOR
        f. Configuration Properties -> C/C++ -> General
                Additional Include Directories ->"E:\Program Files\BREW SDK v2.1.0\inc"
(Note: Please quotes around the directory name, the the directory name contains space ).
        g. Now Apply, and Build the project.

You should get the following Errors:
**********************************
------ Build started: Project: firsthelloworld, Configuration: Debug Win32 ------
Compiling...
AEEModGen.c
AEEAppGen.c
Generating Code...
Compiling manifest to resources...
Linking...
Creating library f:\temp\firsthelloworld\Debug\firsthelloworld.lib and object f:\temp\firsthelloworld\Debug\firsthelloworld.exp
AEEModGen.obj : error LNK2019: unresolved external symbol _AEEClsCreateInstance referenced in function _AEEMod_CreateInstance
f:\temp\firsthelloworld\Debug\firsthelloworld.dll : fatal error LNK1120: 1 unresolved externals
Build log was saved at "file://f:\temp\firsthelloworld\Debug\BuildLog.htm"
firsthelloworld - 2 error(s), 0 warning(s)
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
*********************************

3.4 Building the DLL
--------------------
        a. Now copy helloworld.c from the BREWSDK Examples to the project directory
        b. Add the File to the Project.
                * Right Click on firsthelloworld
                * Add -> Existing Items -> Select the helloworld.c
        c. Change #include "helloworld.bid" to #include "firsthelloworld.bid"
        d. Compile the project. (This should build successfully)
There should be a dll file in Debug Directory

With this you won't be able to run the dll.

3.5 Running the Application
---------------------------
Let us start from scratch. Delete the BREW_Emu.dat in the bin directory of the BREW SDK. This file contains the basic settings.
        a. Create a Directory known a BrewAppRepository or something similar
        b. Create an Environment variable named BREWAPP pointing to the BrewAppRepository. (Refer above document on how to create Envirnment Variables).
        c. Make a directory inside BrewAppRepository as firsthelloworld.
        d. Copy the firsthelloworld.dll from the Debug Directory into the newly created folder.
        e. Copy the firsthelloworld.mif into BrewAppRepository
        f. Now Start->Program Files->BREW SDK xxx->Brew Simulator/Emulator
        g. A Settings Dialog is displayed
        h. Choose the Device as the Initial Device from the Devices Directory of the BREW SDK
        i. Choose BrewAppRepository as the Applet Directory.
        j. Click OK
You should see the able to see the FIRSTHELLOWORLD Application icon. On clicking it, "Hello World" will be displayed.

Now, this requires you manual copy the dll every time you build the dll. And you need to run the emulator from Start->Program files. There many ways to avoid this problem.
        1. Post Build Script
        2. Setting Output Directory
With the above solution, you need to set as to how you want to run the dll.
        * Go to Project properties ( Right Click on firsthelloworld -> Properties )
        * Configuration Properties -> Debugging
                Command = <Select the BREW_Emulator.exe in the bin directory on the Brew SDK> ( In 3.x and greater it is known as BREW_Simulator.exe )
                This is a User Based Setting, that means on every time you copy the project into a different User Space or System, you need to do this setting.
        * Now Press F5 or Debug -> Start Debugging

3.5.1 Post Build Script
        Simple Shell Scripts which will copy the dll to the Brew Applet directory.
        a. Go to Project properties ( Right Click on firsthelloworld -> Properties )
        b. Configuration Properties -> Build Events -> Post-Build Events
                Command Line = copy Debug\firsthelloworld.dll $(BREWAPP)\firsthelloworld\
(Note: I am using Environment Variable)
********************** After every build
Performing Post-Build Event...
1 file(s) copied.
**********************

3.5.2 Setting Output Directory
        a. Go to Project properties
        b. Configuration Properties -> Linker
                Output Directory = $(BREWAPP)\$(ProjectName)\$(ProjectName).dll

3.6 Adding Debug Information
----------------------------
        I have made a copy of the Project File before I started adding Debug Information. ( firsthelloworld.vcproj.withoutDebug )
        a. Go to Project Properties
        b. Configuration Properties -> C/C++ -> General
                * Debug Information Format = Program Database for Edit & Continue
                * Warning Level = Level 4
                * Detect 64-bit Portability Issues = No
        c. Configuration Properties -> C/C++ -> Browse Information
                * Enable Browse Information = Include All Browse Information
        d. Configuration Properties -> Linker -> Debugging
                * Generate Debug Info = YES

3.7 Making it System Independent
--------------------------------
        I have made a copy of the Project File before I make it system Independent
( firsthelloworld.vcproj.systemDependent )
        a. Close VS 2005 Express
        b. Edit the firsthelloworld.vcproj wit a Text Edit ( Notepad, Vi )
        c. Replace all instance of the BREW SDK Directory (say E:\Program Files\BREW SDK v2.1.0) with $(BREWSDK210EN).
        d. Save and exit

4. Important Notes
==================
        a. Always restart the VS 2005 Express after adding a new Environment.
        b. Always close all instance of VS 2005 Express, when you edit the vcproj file using Text Editor


This document is licensed under the Creative Commons Attribution 3.0 Unported License ( http://creativecommons.org/licenses/by/3.0/ )

Saving Electricity - Inspired by Blackle

2007-06-01T12:48:00.001-07:00

For those who are inspired by Blackle and want to invert ( change ) the color of the entire system to black - what are you waiting for!!!

1. Goto Control Panel.
2. Select Display -> Click the Apperance Tab.
3. Choose High Contrast #1 or #2 ( Greeniee Foreground ) in the Color Scheme.
4. Apply and wait for the changes to happen.

Once this is done, you can access Google instead of Blackle.

Sometimes the browser may not use the system default color scheme, for that to happen:
1. Open Browser ( Firefox )
2. Tools menu -> Options
3. Content Tab -> Colors
4. Mark the Use System Color Option
5. Click Ok.

Trickles of Water in the high mountains, together form a mighty river - which joins the great Ocean.

Arrage Icons by CVS Status

2007-05-19T12:43:00.001-07:00

I want Tortoise CVS to arrange icons based on CVS Status. I was not able
to do so. I check up the feature list need find them there. I also check
the features wanted listed, no luck even there. I thought I should add
code to tortoise for this feature. When I was studying some pages for
adding a column on the file explorer. It was here that I found that the
feature already exists.

All you got to do is
1.Click View->Details
2.Right Click on the column header, choose more.
3.Select amoung the CVS Status, CVS Revision, CVS Sticky Tags or CVS
File type
4.Click View->Arrange Icons by->CVS Status
5............There you go, it is ordered by CVS Status ( Modified,
Unmodifed, Unknown, Added, Conflict, Removed )

void __builtin_return_address (unsigned int level);

2006-03-08T09:52:00.000-08:00

void __builtin_return_address (unsigned int level);
Returns the return address of the current function, or of one of its callers. Where level argument is a constant literal indicating the number of frames to scan up the call stack. The level must range from 0 to 63. A value of 0 yields the return address of the current function, a value of 1 yields the return address of the caller of the current function and so on.

Notes:

When the top of the stack is reached, the function will return 0.
The level must range from 0 to 63, otherwise a warning message will be issued and the compilation will halt.
When functions are inlined, the return address corresponds to that of the function that is returned to.
Compiler optimization may affect expected return value due to introducing extra stack frames or fewer stack frames than expected due to optimizations such as inlining.

    __builtin_return_address(0) yields the address to which the current function will return. __builtin_return_address(1) yields the address to which the caller will return, and so on up the stack.
    Return probes operates by replacing the return address in the stack (or in a known register, such as the lr register for ppc - what else can you do with a system with 100's of registers :) ). This may cause __builtin_return_address(0), when invoked from return-probed function, to return the address of the return-probes trampoline. There has been concern that this will break something.
    __builtin_return_address is used entirely for tracing, profiling, and error reporting.

Keeping Deleted Code for Future Reference (with comments)

2006-03-07T12:39:00.000-08:00

Many a times we have come across a situation where we want to
keep a piece of code that does not execute. If often do it with "/*" and
"*/". But these won't work if there are similar comments within the
piece of code we want to comment. It achieve this use "#if 0" and
"

eg:

#if 0

printf ("%d", a);

#endif

Eraser - In Brief

2006-03-06T01:46:00.000-08:00

Multi-threaded programming

* error-prone

* easy to make synch mistakes := data race

* hard to locate synch mistakes in debug

In few Word: Eraser is ?

* dynamically detects data races in lock-based multi-threaded programs

* uses binary rewriting techniques

* monitor every shared memory reference

* verify "consistent" locking behavior/discipline

Introduction

* multi-threaded programs are the common programming techniques

* Dynamic race detection based on "happens-before" relation

* checks conflicting mem accesses from different threads

* Based on locking discipline: programming policy, ensures absence of data races E.g. require every variable shared b/n threads to be protected by a mutual exclusion lock

Definitions

* Lock : synch object; used for mutex; either available or owned by a thread

= ops on lock L: lock(L); unlock(L)

= is essentially a binary semaphore ,but ONLY lock's owner can release that lock

* Data Race : when two (or more) concurrent threads access a shared var

= at least one access is a write AND

= the threads use no explicit mech to prevent the accesses from being simultaneous

= If a prog has a potential data race, then the impact of conflicting accesses to the shared var *will depend on the interleaving* (of the thread executions)

Related Work ? Monitors

* group of shared vars + procedures that are allowed to access those vars

* single "anonymous" lock (by which we mean implicit)

* whenever one of those procedures is entered, that lock is acquired & whenever one of those procedures is exited, the lock is released

* the shared vars in the monitor are invisible outside of the monitor

* provide a static, compile-time guarantee that shared vars are

* serialized and thus free from data races

* Don't protect against data races in progs with dynamically allocated shared vars

Happens-Before Relation

* The HB order is a partial order on all events of all threads in a concurrent execution.

* W/in any single thread: events ordered in order in which they occur.

* B/n threads, events ordered according to the properties of the synch objects they access;

= if thread T1 accesses synch object L1 and the next access to L1 is by T2 then the T1's access of L1 "happens before" T2's

= if two (or more) threads access a shared var and the accesses are NOT ordered by the happens-before relation, then in another exec of the prog, the two accesses could have happened simultaneously == a data race could have occurred

# If there were no happens-before relation b/n T1's unlock(L) and T2's lock(L) then T1 could have read v = 3; T2 could have read v = 3; then T1 would write v = 4; so would T2 (which is not what SHOULD have happened had those two variable assignments been serialized)

Drawbacks to tools based on HB

* inefficient; require per-thread info a/b concurrent accesses to all shared mem locs

* effectiveness of tools based on HB is highly dependent upon the interleaving produced by the scheduler

Interleaving produced by the Scheduler

* Thread 1

y++ //y1

* Thread 2

y++ //y2

* So possible orderings (y_1 comes before A; y_2 comes after B):

= y_1, A, B, y_2

= y_1, B, A, y_2

= y_1, B, y_2, A

= B, y_1, A, y_2

= B, y_1, y_2, A <=== potential data race

= B, y_2, y_1, A <=== potential data race

The Lockset algo

* enforces simple locking discipline: "every shared var must be protected by some lock?

= the lock is held by the thread accessing the var *when* that thread accesses the shared var

* Eraser monitors all reads and writes as the program executes; infers protection relation (b/n particular locks & specific vars) from execution history (since it does not know which lock protects which shared var)

* V => shared var

* C(V) => candidate locks for V

* as would expect, when new var V is initialized, its candidate set, C(V), includes all possible locks

* when V is accessed, it updates C(V) with the intersection of C(V) and the set of locks held by the current thread => "lockset refinement?

* if C(V) becomes empty, then this indicates that there is no lock that consistently protects V. (error)

The Lockset algo V.1

* Let locks held(t) be the set of locks held by thread t.

* For each v, initialize C(v) to the set of all locks.

* On each access to v by thread t,

= set C(v) := C(v) ? locks held(t);

= if C(v) := { }, then issue a warning.

Improving the Locking Discipline

* Three cases violate the discipline but don't have data races

= Initialization: shared vars are frequently initialized w/o holding a lock

= Read-shared data: some shared vars are written during init only and are read-only thereafter; is OK to have multiple readers simultaneously reading

= Read-write locks: read-write locks allow multiple readers to access a shared var but only ONE writer to do so

Accommodating Initialization

* by delaying refinement of a variable's candidate after that var has been initialized

* how to know when initialization is complete?

= Eraser says a shared var has been initialized at the instant that var is first accessed by a second thread (Virgin)

= As long as a var has been touched by a single thread only, all reads & writes of that var are considered part of initialization (Exclusive). C(V) is not refined here

Accommodating Multiple-Readers

* A read access from another state changes the state of the variable to shared

* C(V) is refined, but errors are not reported even if C(V) is null

* Accommodating Read-Write

* A write by another thread on a shared var, takes the var from Exclusive or shared state to shared-modified

* C(V) is refined and error is reported if C(V) is null

* Require that for every variable V, some lock M protects V

= M is held in write-mode for every write of V

= M is held in *some* mode (read or write) for every read of V

The Lockset algo V.2

* keep track of all locks held by thread T; locks_held(T)

* keep track of locks held in write mode by T; write_locks_held(T)

* Upon entering the Shared-Modified, C(V) = set of all locks

= If we are READING V, C(V) = C(V) intersection locks_held(T)

= If we are writing V, C(V) = C(V) intersection write_locks_held(T)

= if C(V) == {}, report error

Implementation

* Eraser takes an unmodified program binary as input and adds instrumentation to produce a new binary that is functionally equivalent but that includes calls to the Eraser runtime to implement the Lockset algo

* To maintain C(V), Eraser instruments each load & store in the program

* To maintain locks_held(T) for each thread T, Eraser instruments each call to acquire or release a lock as well as the stubs used to manage thread initi & finalization.

* To initialize C(V) for dynamically allocated data, Eraser instruments each call to the storage allocator

* Eraser treats each 32-bit word in the heap or global data as a possible shared var

* Eraser does NOT instrument loads & stores whose address mode is indirect off the stack pointer -- since these are presumed to be stack refs which are presumed to be local to the thread data, not global data (which will be in a global location or in the heap).

* Eraser maintains candidate sets for stack locations that are accessed via registers *besides* the stack pointer

Representing Candidate Lock Sets

* naive implem: store a list of candidate locks for each mem loc

* exploit: distinct sets of locks observed in practice is small

= represent each set of locks by an int (lockset index)

= lockset index indexes into a table whose entries represent the set of locks as sorted vectors of lock addresses

= each entry represents some set of locks stored as a vector where that vector is sorted by the addresses of the locks comprising the set

= use hashing to eliminate dupes in the table & to find the key for a given set of locks

= the entries in the table are never deallocated nor modified; lockset index valid for program's lifetime

= Eraser caches result of several set intersections so fast case for set intersection is just a table lookup

= each lock set is -- again -- stored as a sorted vector so the worst case, intersection can be performed by comparing two sorted vectors

* For every 32-bit word in the data segment or in the heap, there is a shadow word that contains

= the 30-bit lockset index for that word

= a 2-bit state condition (Virgin, Exclusive, Shared, Shared-Modified).

= In the Exclusive state the 30 bits are used to store the ID of the thread with exclusive access.

* All the std. mem alloc routines are instrumented to allocate and initialize a shadow word for each word allocated by the prog.

* When a thread accesses a mem loc, Eraser finds the shadow word for that mem loc by adding some fixed displacement to the memory location's

Annotations

* How to suppress false positives without eliminating true positives?

* If false alarms suppressed with accurate & specific "annotations,? then when a prog is modified and modified prog is tested, only "fresh and relevant" warnings will be produced

Kinds of False Alarms

* mem reuse: mem is reused w/o resetting shadow var

= many progs implement free lists or private allocators so now way for Eraser to know that some piece of memory has been "privately recycled" (and thus is protected by a *new* set of locks) must be accommodated

= EraserReuse(address,size)

= instructs eraser to reset the shadow mem corresponding to the mem range to the Virgin state

* Private locks:

= locks taken w/o communicating this seizure to Eraser

= caused by private implems of multiple-reader, single-writer locks (not part of pthreads i/f that Eraser implements)

= EraserReadLock(lock)

= EraserReadUnlock(lock)

= EraserWriteLock(lock)

= EraserWriteUnlock(lock)

= communicate private lock implementations

* Benign races:

= true data races; didn't affect program's correctness

= some intentional, others no

= EraserIgnoreOn()

= EraserIgnoreOff()

= surround code which the race detector should not worry about w.r.t. finding races

Additional Thoughts/Works

* Protection by multiple locks

* Deadlock

Protection by multiple locks

* Some programs protect a shared variable by multiple locks instead of single

* Working :

= any writer must hold all locks for a shared var

= any reader must hold at least one lock for a shared var

= aimed at avoiding dead lock

* modified Lockset in following manner:

= On each read of V by T,

= if C(V) == {}, issue warning

= On each write of V by T,

= set C(V) == C(V) intersect locks_held(T)

= if C(V) == {}, issue warning

* prevented false alarms, could also cause false negatives

= if T1 reads V while holding M1 and T2 writes V while holding M2

= violation of locking discipline will only be reported if the write preceeds the read

* requires complex DSs: sets of sets of locks

Deadlocks

* Discipline to avoid deadlock:

= choose partial ordering among all locks

= and program each thread so that whenver it holds more than one lock, it acquires them in increasing order (prevents Circularity requirement of deadlock).

* deadlock checking could be useful addition to Eraser