Certificate Pinning in Android

Background

Generally what happens in a https connections is that client asks for SSL certificate from the SSL compliant server it is communicating with over https. Server will provide a certificate from it's key store. After client receives this certificate it validates it's credentials depending on whether

• hostname is same as requested
• has a verifiable chain of trust back to a trusted (root) certificate [from clients trust store]

Now if connections are proxied and you can get the device to trust your (rogue) root CA certificate then you can intercept the secure connections. This is essentially man-in-the-middle attack. Now here is what happens in SSL pinning which potentially adds an extra security layer from man-in-the-middle attacks-

App bundles the known server certificates with it. When app tries to make a secure connection with the server, it validates the certificate received by the server with the ones it has bundled with. So even if OS validates the received certificate chain against a (potentially rogue) root CA, the app will reject the connection displaying network error.

Common type of certificates

In summary, there are four different ways to present certificates and their components:

1.  PEM Governed by RFCs, it's used preferentially by open-source software. It can have a variety of extensions (.pem, .key, .cer, .cert, more)
2. PKCS7 An open standard used by Java and supported by Windows. Does not contain private key material.
3. PKCS12 A private standard that provides enhanced security versus the plain-text PEM format. This can contain private key material. It's used preferentially by Windows systems, and can be freely converted to PEM format through use of openssl.
4. DER The parent format of PEM. It's useful to think of it as a binary version of the base64-encoded PEM file. Not routinely used by much outside of Windows.

NOTE :
PEM on it's own isn't a certificate, it's just a way of encoding data. X.509 certificates are one type of data that is commonly encoded using PEM.

PEM is a X.509 certificate (whose structure is defined using ASN.1), encoded using the ASN.1 DER (distinguished encoding rules), then run through Base64 encoding and stuck between plain-text anchor lines (BEGIN CERTIFICATE and END CERTIFICATE).

You can represent the same data using the PKCS#7 or PKCS#12 representations, and the openssl command line utility can be used to do this.

Convert a PEM-formatted String to a java.security.cert.X509Certificate

public static X509Certificate parseCertificate(String certStr) throws CertificateException{

    //before decoding we need to get rod off the prefix and suffix
    byte [] decoded = Base64.decode(certStr.replaceAll(X509Factory.BEGIN_CERT, "").replaceAll(X509Factory.END_CERT, ""));

    return (X509Certificate)CertificateFactory.getInstance("X.509").generateCertificate(new ByteArrayInputStream(decoded));
}

How to get PEM certificate of the SSL/https compatible site

1. Go to that particular website  on your browser. Lets say we go to - 
• https://www.ssllabs.com/
2. Now look at the top left of the URL bar. You should see details of the connection. And certificate details if your connection is https -
   
   
   
   
   
   
   
   
3. Next click on view certificate and click on Details -
   
   
   
   
   
4. Now click on Export and save your file is PEM format -
   
   

You can find app for this ready in playstore -

• https://play.google.com/store/apps/details?id=com.osfg.certificatepinning

Related Links

• What is a Pem file and how does it differ from other OpenSSL Generated Key File Formats?
• What is certificate pinning?
• Convert a PEM-formatted String to a java.security.cert.X509Certificate(SO) 
• Intercepting Android network calls using Fiddler Web Proxy(OSFG)
• How to resolve “enter the password for credential storage” issue?(SO)
• Android Cert pinning demo App in Playstore 
• Certificate and Public Key Pinning (OWASP)

Unprotected private key file error while connecting to AWS via SSH

Background

In one of the previous posts, we saw how to connect to your AWS instance.

• Launching and connecting to your new EC2 instance of your Amazon web service

In that post, we saw how you can remotely connect to your instance using ssh (putty on windows). Recently I migrated to Mac and got following error for connecting.

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@         WARNING: UNPROTECTED PRIVATE KEY FILE!          @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Permissions 0777 for 'Documents/Softwares/athakur-securekey.pem' are too open.
It is required that your private key files are NOT accessible by others.
This private key will be ignored.
bad permissions: ignore key: Documents/Softwares/athakur-securekey.pem
Permission denied (publickey).

See screenshot below -

So how do you resolve this?

Solution

You need to give read/write permission just to that user (no groups or other users). So running following command should suffice -

• chmod 600 athakur-securekey.pem

OR alternatively

• chmod u=rw athakur-securekey.pem 
• chmod go=  athakur-securekey.pem

Quoting from AWS documentation -

• Use the chmod command to make sure your private key file isn't publicly viewable. For example, if the name of your private key file is my-key-pair.pem, use the following command:
• chmod 400 /path/my-key-pair.pem 
•  

Related Links

• WARNING: UNPROTECTED PRIVATE KEY FILE! when trying to SSH into Amazon EC2 Instance (SO)
• AWS documentation  
• Launching and connecting to your new EC2 instance of your Amazon web service 

Use of final local variables in Java

Background

We know why we declare a instance variable or class or a method as final. So that it cannot be extended or modified or overridden. But there are instances when we declare final local variables i.e declare variables inside method as final. Why would we do that? Let's see that.

To understand the usage I had asked this very question on Stack Overflow and Jon Skeet had answered it which made sense - 

There's one important "feature" of final local variables: they can be used in local (typically anonymous) inner classes. Non-final local variables can't be. That's the primary use of final for local variables, in my experience.

public void foo() {
    final String x = "hello";
    String y = "there";

    Runnable runnable = new Runnable() {
        @Override public void run() {
            System.out.println(x); // This is valid
            System.out.println(y); // This is not
        }
    };
    runnable.run();
}

Note that as a matter of style, some people like to use final even when they're not capturing the variable in a local inner class. I'd certainly be comfortable with final being the default, but a different modifier for "non-final", but I find that adding the modifier explicitly everywhere is too distracting.

NOTE : Well behind the scenes, the compiler generates an instance variable in the anonymous inner class and copies the value of the original variable when the instance is created. 

Java 8 Changes

The compiler is generating a class file from your inner class. A separate class has no way to refer to local variables. If the local variable is final ,Java can handle it by passing it to the constructor of the inner class or by storing it in the class file. If it weren’t effectively final, these tricks wouldn’t work because the value could change after the copy was made. 

Up until Java 7, the programmer actually had to type the final keyword. In Java 8, the “effectively final” concept was introduced. If the code could still compile with the keyword final inserted before the local variable, the variable is effectively final. 

Note same applies for Lambda expressions. To use a local variable in a lambda expression it needed to be final or effectively final.

As far as performance is considered there should not be much difference as JVM does it's own optimizations depending on the usage in code.

Nested classes in Java Summary

Related Links

• Use of final local variables in java (SO)
• Does use of final keyword in Java improve the performance? (SO)
• Using Lambda Expressions from Java 8  (OSFG)

Iterator Design Pattern

Background

In one of the previous posts we saw Introduction to Design Patterns. In that we learned how different design patterns solve some pre identified design concerns and provide a good solution. Above post also states types of design patterns and links to design patterns we have already covered. In this post we will see another design patter - Iterator pattern. Is it same as the iterator I use to iterate over collections? Yes it is! And that a design pattern? What problem does that solve? Hold on to that we will come there in some time :)

Problem

Lets say there are two companies - Company A and company B. They both maintain employee records for their respective employees and their implementation is something like below - 

Company A Employee records - 

/**
 * 
 * @author athakur
 *
 */
public class CompanyAEmpRecords {

    private Employee[] companyEmployees = new Employee[10];
    private int index = -1;

    public void addEmployee(Employee newEmployee) {
        if (index == 10) {
            throw new RuntimeException("Maximum employee limit reached");
        }
        companyEmployees[index++] = newEmployee;
    }

    public void removeEmployee(String name) {
        // implementation to remove employee
    }

    public int getNoOfEmployees() {
        return index + 1;
    }
    
    public Employee[] getEmployees() {
        return companyEmployees;
    }

}

Company B Employee records - 

/**
 * 
 * @author athakur
 *
 */
public class CompanyBEmpRecords {
    private List<Employee> companyEmployees = new ArrayList<>();

    public void addEmployee(Employee newEmployee) {
        companyEmployees.add(newEmployee);
    }

    public void removeEmployee(String name) {
        // implementation to remove an employee based on name
    }

    public int getNoOfEmployees() {
        return companyEmployees.size();
    }
    
    public List<Employee> getEmployees() {
        return companyEmployees;
    }

}

Life was all good when they were working independently. Company A was small and sufficient with less than 10 employees where as Company B did not really care how many employees joined. But then one day they decided to merge and expand their business. Employees of both the companies will now be under one entity and the task to create code that lists down both company's employees now rests on you. You know both Employee record implementation of companies. So you start writing code using it.

/**
 * 
 * @author athakur
 *
 */
public class CompanyRecordsPrinter {
    
    public void pringCompanyEMployeeRecords(CompanyAEmpRecords companyAEmpRecords, CompanyBEmpRecords companyBEmpRecords) {
        
        Employee[] companyAEmployees = companyAEmpRecords.getEmployees();
        for(int i=0; i< companyAEmpRecords.getNoOfEmployees();i++) {
            System.out.println(companyAEmployees[i]);
        }
        
        List<Employee> companyBEmployees= companyBEmpRecords.getEmployees();
        for(Employee emp : companyBEmployees) {
            System.out.println(emp);
        }
        
    }

}

Well that serves the purpose. We are printing employees in both companies using their records. But is it a good design. Two loops for two different types of data structures. What if Company C is merged with this later. Add a new loop to handle it? Naah. Something does not feel right. This is where iterator pattern comes into picture.

Iterator Pattern defined

The Iterator pattern provides a way to access the elements of an aggregate object sequentially without exposing it's underlying representation.

Solution

You will basically have a common interface called Iterator which will have methods like -

• boolean hasNext()
• Object next()

Each Employee Record class will have a method called getIterator() that will basically return corresponding new instance of Iterator. Lets call it -

• CompanyAEmpRecordsIterator
• CompanyBEmpRecordsIterator

Then you can have a common method that take an Object of type Iterator and iterate over it using hasNext() method and get the actual data using next() method.

Sample code -

public class CompanyAEmpRecords implements CompanyEmpRecords {

    private Employee[] companyEmployees = new Employee[10];
    private int index = -1;

    @Override
    public void addEmployee(Employee newEmployee) {
        if (index == 9) {
            throw new RuntimeException("Employees limit reached");
        }
        companyEmployees[++index] = newEmployee;
    }

    @Override
    public void removeEmployee(Employee oldEmployee) {
        int i = 0;
        for (; i <= index; i++) {
            if (companyEmployees[i].equals(oldEmployee)) {
                break;
            }
        }
        for (int j = i; j <= index - 1; j++) {
            companyEmployees[j] = companyEmployees[j + 1];
        }
        companyEmployees[index] = null;
        index--;

    }

    @Override
    public int getNoOfEmployees() {
        return index + 1;
    }

    @Override
    public Iterator getIterator() {
        return new CompanyAEmpRecordsIterator();
    }

    private class CompanyAEmpRecordsIterator implements Iterator {

        int currIndex = -1;

        @Override
        public boolean hasNext() {
            if (currIndex + 1 <= index)
                return true;
            else
                return false;
        }

        @Override
        public Object next() {
            if (currIndex + 1 <= index)
                return companyEmployees[++currIndex];
            else
                return null;
        }

    }

}

You get the point.  And your printing logic will be as simple as  -

    public void pringCompanyEMployeeRecords(CompanyAEmpRecords companyAEmpRecords, CompanyBEmpRecords companyBEmpRecords) {
        
        printRecord(companyAEmpRecords.getIterator());
        printRecord(companyBEmpRecords.getIterator());
    }
    
    private void printRecord(Iterator recordIterator) {
        while(recordIterator.hasNext()) {
            System.out.println(recordIterator.next());
        }
    }

This is just the snippet I have provided. You can download the complete code from my git repository -

• Iterator Design Pattern Demo (GIT)

NOTE : Instead of defining your own iterator interface you can use java.util.Iterator interface instead.

NOTE :  we have not added remove() method in the Iterator interface. Neither are we handling multi threading scenarios like what happens when the collection gets modified when you are iterating using that iterator. The way this is handled is that when iterator is created we copy the modcount (modification count) and at any point during the iteration this is different than the original count we throw java.util.ConcurrentModificationException.

For sample code you can refer to Iterator provided by ArrayList class in Java -

    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

Modification count and ConcurrentModificationException

Lets try to understand modcount we just discussed above in a better way. Now a collection when initialized has a variable called

protected transient int modCount = 0;

This keeps track of modifications made to the collection. Now when you create an iterator for your collection this modcount gets copied over to your iterator as expectedModCount -

int expectedModCount = modCount;

Now during each iterator of iterator checkForComodification() method is called which does following -

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

So if modCount of the collection is not same as what was copied over to it's iterator during it's creation (stored as expectedModCount) then it throws ConcurrentModificationException.

Exception for this is when you use iterators remove method in which case iterator updates it's expectedModCount accordingly.

Class Diagram

Related Links

• Introduction to Design Patterns(OSFG)
• Iterator Design Pattern Demo (GIT)
• Why and when can we encounter ConcurrentModificationException in Java(OSFG)  

Tips and Tricks for your MacBook

• Keyboard shortcut to lock your screen
• Control+Shift+Eject is the keystroke for Macs with an Eject key, and for external keyboards.Control+Shift+Eject is the keystroke for Macs with an Eject key, and for external keyboards.
• Control+Shift+Power is the keystroke for Macs without the eject key, like the MacBook Air and MacBook Pro Retina.
• set host name in mac

• sudo scutil --set HostName name-you-want
• Take screenshot
• Press Command + Shift +3 (for whole screen)
• Press Command + Shift + 4
• Move the crosshair pointer to where you want to start the screenshot.
• (for window screenshot) Press the Space bar. The pointer changes to a camera pointer
• Drag to select an area. ...
• When you've selected the area you want, release your mouse or trackpad button. ... 
• NOTE : screenshots will be saved on your desktop 
• Install  Homebrew - Package manager for OS X.Homebrew installs the stuff you need that Apple didn’t.
• /usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"
• git link - https://github.com/Homebrew/homebrew-core
• Install gradle -  brew install gradle
• To downgrade or move your app to new version you can use
• Homebrew install specific version of formula?(SO)
• To upgrade any brew module do following -
• brew update
• brew upgrade gradle 

 

 
• Install nodejs and npm - brew install node  
• Install wget - brew install wget
• Enable and Use the ‘locate’ Command in the Mac OS X Terminal - Run following in console

•  sudo launchctl load -w /System/Library/LaunchDaemons/com.apple.locate.plist 
• NOTE :  It will take time for database to build
• Show Desktop : The default is F11. On a MacBook you will have to press fn + F11, as the keys are used for controlling volume by default. OR Use ⌘ + F3 on Mavericks and newer Macbook Pros. You can find more keyboard mappings in System Preferences -> Keyboard -> Shortcuts
  
• To set environment variable for your user you can add it in ~/.bash_profile file. If it is not present you can create one. You can also set aliases here
• vi  ~/.bash_profile
• -------file content start-------
• export ANDROID_HOME=/Users/athakur/Library/Android/sdk
• export JAVA_HOME=/Library/Java/JavaVirtualMachines/1.6.0.jdk/Contents/Home/
• export DYLD_LIBRARY_PATH=/Users/athakur/Documents/Softwares/instantclient_12_1
• export PATH=$PATH:$ANDROID_HOME/platform-tools/:$DYLD_LIBRARY_PATH/:/usr/local/Cellar/subversion/1.9.4/bin/
• alias ll='ls -la'
• ------- file content end-------
• Lastly don't forget source ~/.bash_profile to reload profile.
• To verify you can execute echo $PATH
• If you are not able to see external drives in your Finder go to Finder -> Preferences -> Sidebar and make sure External Disks are ticked under Devices section.
  
  
• If you want to change default applications your  files open with you can follow my separate post - How to change default apps to open files with on the Mac(OSFG)  
• If you are not able to access links while converting doc to pdf in mac refer - Resolving issue of losing links when saving word document to PDF in Mac (OSFG) 
• There are multiple ways you can arrange and sort files in your Finder. You can right click and select "Show View options" and customize as per your wish -
  
  
  
  
  
  
  
  
  
• Unlike the ZIP files, Apple’s MAC OS X does NOT include a built-in archive utility tool that you can easily use to open RAR files. Apple’s archive utility upports a number of file formats like ZIP, TAR and GZIP. It does not support RAR files.
• You can use unrar utility for this. To install it using homebrew type following commands 
• install : brew install unrar
• unrar : unrar x <filename>
• list files : unrar l archive.rar
• Cider : TransGaming Technologies has developed a product called Cider which is a popular method among publishers to port games to Mac[citation needed]. Cider's engine enables publishers and developers to target Mac OS X. It shares much of the same core technology as TransGaming's Linux Portability Engine, Cedega. Public reception of games ported with Cider is mixed, due to inconsistency of performance between titles; because of this, “Ciderized” games are neither seen as the work of cross-platform development, nor as native, optimized ports. Both Cider and Cedega are based on Wine. Electronic Arts announced their return to the Mac, publishing various titles simultaneously on both Windows and Mac, using Cider. 
• To Show hidden files and folders in Finder (Youtube)
• run 'defaults write com.apple.finder AppleShowAllFiles YES' in command prompt 
• relaunch Finder (Hold option button + right click on Finder and select relaunch)
•  Soundflower : This is an Inter-application Audio Driver. Soundflower is a virtual audio device that provides an easy and simple way for Max/MSP and other applications
  to send and receive audio to and from any other application.  Running with very low latency and cpu usage, Soundflower allows each client application to use its usual buffer size.
• You can get it here.
• TBC...

Videos

Related Links

• Please share your hidden OS X features or tips and tricks
• How to change default apps to open files with on the Mac(OSFG)  
• Resolving issue of losing links when saving word document to PDF in Mac (OSFG)  
• Homebrew install specific version of formula?(SO) 
• How to view hidden files in Mac(Youtube)
• Install Oracle instant client and sqlplus using Homebrew(OSFG) 
• How to enable touch to click on your Mac(OSFG)

Greasemonkey script to replay Youtube videos once they finish

Background

In one of the previous post we saw a Greasemonkey script to block Game of thrones spoiler on facebook.  In this post we will see Greasemonkey script to replay Youtube videos once they finish. And we will see how to do this from very beginning including installing the plugin.

Setup

First step is to install the  Greasemonkey  plugin in firefox. There is a similar plugin in chrome called Tampermonkey. For demo purposes we will use firefox. So go ahead and install the plugin. URL is -

• https://addons.mozilla.org/en-US/firefox/addon/greasemonkey/

Once installed you can see it's icon besides navigation bar. There you can click to create a new user script -

Then you should see a window where you can create your script.

You can find the actual script on my github account - 

• youtube-replayer.js (github)

Related Links

• Greasemonkey script to block Game of Thrones spoilers(OSFG)
• youtube-replayer.js (github)

Locking and Visibility in Java Multithreaded programs

Background

In one of the previous post on Race Condition, Synchronization, atomic operations and Volatile keyword we saw what is race condition, how can we use synchronization to avoid it. We also saw what is volatile variables and what are they used for. Though that post speaks a lot about multi threading issues and it's solution I am writing this post to get even a clearer perspective.

This post is more about memory visibility meaning it is about reading stale values rather than worrying about race conditions.

Issue : Each thread has it's own stack and own cache where values are cached for faster access. Though this is a feature used for performance it can led to undesirable results. Lets say there is a mutable value that is shared among two threads. If one thread modifies it's value and thread two tries to do a subsequent read, it is not guaranteed that thread 2 will read the modified value. This may be because of caching data in threads.

JVM may reorder read/writes for optimizations. Understand we are not talking about race condition here at all. Even if the operations were atomic this issue would happen. So the issue is about memory visibility of a mutable object across threads and the challenge is to get the latest/correct value in read which followed a write.

Issue 2 (Non atomic 64bit operations) : Java memory model required fetch and store operations to be atomic . Exception is for non volatile long and double data types where JVM is permitted to treat a 64 bit read/write operations as two separate 32 bit operations. So reads and writes for these happen in different threads read can give high 32 bits of one value and lower 32 bits of another.[Solution : declare non atomic double and long data types as volatile or guard them with a lock]

Solution to Memory visibility issue

We saw the issue with memory visibility. Now lets see how we can resolve this.

Intrinsic locks guarantee that one thread will see the changes made by another thread in a predictable manner. So lets say in a synchronized region thread T1 makes some changes and then thread T2 enters the same critical region (after T2 releases the lock of course) then T2 is guaranteed to see changes made by T1. So the issue we discussed above will not occur i.e no stale values.

Summing it up : Locking is not just about atomicity i.e making compound operations atomic but it is also about memory visibility. To ensure all threads see latest updated value of shared mutable variable, reading and writing threads must be synchronized on a common lock.


Another solution ofcourse is to make shared mutable variables volatile. I am not going to discuss volatile here. You can refer the previous post for details -  Race Condition, Synchronization, atomic operations and Volatile keyword.[Volatile keyword guarantees that all reads of a volatile variable are read directly from main memory, and all writes to a volatile variable are written directly to main memory]

Related Links

• Race Condition, Synchronization, atomic operations and Volatile keyword(OSFG).

Remove duplicate rows from table in Oracle

Background

This is classic database question to check candidates knowledge about SQL queries. You have a table where lets say you have duplicate entries (lets also say column1 and column2 can form a candidate key). Now you need to remove duplicates from then table. That is all rows in the table should be distinct. How would you do this?

 Query to remove duplicate rows from table in Oracle

You can execute following query to remove duplicates - 

DELETE FROM your_table
WHERE rowid not in
(SELECT MIN(rowid)
FROM your_table
GROUP BY column1, column2);

column 1 and column2 as I mentioned for candidate keys. You can very well add all columns in it.

Example

Queries :

create table schema8.EMPLOYEE(ID int, name varchar2(255));
insert into schema8.EMPLOYEE values(1,'Aniket');
insert into schema8.EMPLOYEE values(1,'Aniket');
insert into schema8.EMPLOYEE values(1,'Aniket');
insert into schema8.EMPLOYEE values(2,'John');
insert into schema8.EMPLOYEE values(2,'John');
insert into schema8.EMPLOYEE values(3,'Sam');
insert into schema8.EMPLOYEE values(3,'Sam');
insert into schema8.EMPLOYEE values(3,'Sam');

ROWID Pseudocolumn  in Oracle

For each row in the database, the ROWID pseudocolumn returns the address of the row. Oracle Database rowid values contain information necessary to locate a row.

Rowid values have several important uses:

• They are the fastest way to access a single row.
• They can show you how the rows in a table are stored.
• They are unique identifiers for rows in a table.

NOTE : You should not use ROWID as the primary key of a table. If you delete and reinsert a row with the Import and Export utilities, for example, then its rowid may change. If you delete a row, then Oracle may reassign its rowid to a new row inserted later.

NOTE : Although you can use the ROWID pseudocolumn in the SELECT and WHERE clause of a query, these pseudocolumn values are not actually stored in the database. You cannot insert, update, or delete a value of the ROWID pseudocolumn.

Related Links

• Removing duplicate rows from table in Oracle
• ROWID Pseudocolumn  
• Basic PL/SQL syntax and query executions on Oracle 11g R2 database(OSFG)  
• How does database indexing work?(OSFG)
• Select top N records from each category in PL/SQL (OSFG)

ReentrantLock in Java

ReentrantLocks

Lets me first try to explain reentrancy concept in a simplistic and generic way. We will come to Java specific details a bit later. Reentrancy is lay man terms means ability to enter again. In terms of thread it mean thread can acquired same lock again without blocking itself. Refreshing our multi threading concepts here. When you synchronize over an object the thread obtains a lock on it before entering the critical region (inside synchronized block) and till this thread releases this lock no other thread can acquire it and enter the critical region. 

NOTE : We do this to make compound operations atomic so that there is no race condition or invalid state.

But what happens when we call an synchronized instance method from inside another synchronized instance method. Eg - 

public class TestClass {

    public synchronized void method1() {
        // some code
        method2();
    }

    public synchronized void method2() {
        // some other code
    }

}

Here for a thread to enter either of the method has to obtain a lock on the instance (this) before entering the method. Now we are calling method 2 from method1 which is again synchronized with same instance (this). So thread will try to acquire lock again. If locks were not reentrant in nature we would have ended up in deadlock. 

Note : In Java all intrinsic locks are reentrant in nature. 

Note : Synchronization is built around an internal entity known as the intrinsic lock or monitor lock. (The API specification often refers to this entity simply as a "monitor.") Intrinsic locks play a role in both aspects of synchronization: enforcing exclusive access to an object's state and establishing happens-before relationships that are essential to visibility.Every object has an intrinsic lock associated with it. Explicit locks are introduced in Java 1.5 like semaphore, cyclic barrier etc.

Now lets see Reentant lock in Java that was introduced in Java 1.5.

ReentrantLock  in Java

As per Java doc

A reentrant mutual exclusion Lock with the same basic behavior and semantics as the implicit monitor lock accessed using synchronized methods and statements, but with extended capabilities like -

•  It takes a fairness parameter. When set true, under contention, locks favor granting access to the longest-waiting thread. Otherwise this lock does not guarantee any particular access order. Programs using fair locks accessed by many threads may display lower overall throughput (i.e., are slower; often much slower) than those using the default setting, but have smaller variances in times to obtain locks and guarantee lack of starvation. Note however, that fairness of locks does not guarantee fairness of thread scheduling. Thus, one of many threads using a fair lock may obtain it multiple times in succession while other active threads are not progressing and not currently holding the lock. Also note that the untimed tryLock method does not honor the fairness setting. It will succeed if the lock is available even if other threads are waiting - ReentrantLock(boolean fair)
• It provides tryLock() method which acquires lock only if it is not held by other threads. We can also use timeout with this method which means thread will time out of waiting if lock is not acquired till the timeout value. This is better than intrinsic locks where you have to wait indefinitely.
• It also provides facility to interrupt thread while waiting using.  ReentrantLock provides a method called lockInterruptibly() [Acquires the lock unless the current thread is interrupted.], which can be used to interrupt thread when it is waiting for lock.
• Lastly it also provides functionality to get list of all threads waiting for the lock - getWaitingThreads(Condition condition)
  (Returns a collection containing those threads that may be waiting on the given condition associated with this lock).

NOTE : This lock supports a maximum of 2147483647 recursive locks by the same thread. Attempts to exceed this limit result in Error throws from locking methods.

Example -

 class Test {
   ReentrantLock reLock = new ReentrantLock();
   // ...

   public void m() {
     reLock.lock();  // block until condition holds
     try {
       // ... method body
     } finally {
       reLock.unlock()
     }
   }
 }

Working

Also, the way reentrancy is achieved is by maintaining a counter for number of locks acquired and owner of the lock. If the count is 0 and no owner is associated to it, means lock is not held by any thread. When a thread acquires the lock, JVM records the owner and sets the counter to 0.If same thread tries to acquire the lock again the counter is incremented, and when the owning thread exist synchronized block counter is decremented. When count reaches 0 again lock is released.

Most generic example are Segments used in ConcurrenHashMap. Each segment is essentially a ReentrantLock that allows only single thread to access that part of the map. You can refer to the link above to see how it works. Adding relevant snippet here -

static final class Segment<K,V> extends ReentrantLock implements Serializable {

    //The number of elements in this segment's region.
    transient volatile int count;
    //The per-segment table. 
    transient volatile HashEntry<K,V>[] table;
}

V put(K key, int hash, V value, boolean onlyIfAbsent) {
    lock();
    try {
        //logic to store data in map
    } finally {
        unlock();
    }
}

NOTE : ReentrantLock was introduced since Java 5.

Related Links

• 'Reentrancy' in java (SO)
• Why use a ReentrantLock if one can use synchronized(this)?(SO)
• ReentrantLock JavaDoc
• How ConcurrentHashMap Works Internally in Java(OSFG) 
• Counting Semaphore, CountDownLatch, CyclicBarrier - synchronization methods for concurrency(OSFG)

Implementing blocking queue in Java

Blocking Queue

Blocking queue is a queue that has a limit of elements it can hold and once that limit has reached enqueuing thread needs to wait for some thread to dequeue elements and make space. Similarly if queue becomes empty then dequeuing thread  has to wait until some thread enqueues elements in it.

Diagrammatically it is as follows -

Lets see how can we implement it in Java.

Blocking queue implementation in Java

 Code is as follows - 

package com.osfg.models;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 
 * @author athakur
 * Model class for blocking queue
 */
public class BlockingQueue<E> {
    
    private Queue<E> bQueue = new LinkedList<E>();
    private int maxQueueSize; 
    
    public BlockingQueue(int maxQueueSize) {
        this.maxQueueSize = maxQueueSize; 
    }
    
    public synchronized void enqueue(E e) throws InterruptedException {
        
        while(bQueue.size() == maxQueueSize) {
            wait();
        }
        bQueue.add(e);
        // notify if any thread is waiting to dequeue as data is now available
        notifyAll();
    }
    
    public synchronized E dequeue() throws InterruptedException{
        
        while(bQueue.size() == 0) {
            wait();
        }
        E e = bQueue.remove();
        notifyAll();
        return e;
        
    }

}

Notice how we are using wait() and notifyAll() calls. Also observer both enqueue and dequeue methods are synchronized. So at a time only one thread can execute them. You can also find this code in my data structure github repository. Also see the Thread Pool implementation in Java which uses the blocking queue internally.


Producer - Consumer design can be built using blocking queue. Producers enqueue jobs in the queue and wait when the queue is full where as consumers dequeue jobs in the queue and wait when the queue is empty. Famous example of producer consumer design in Thread pool implementation where you can enqueue your tasks in the queue and threads from Threadpool will dequeue and process it. As mentioned before you can see the code for blocking queue and thread pool in my github repository (Links in Related Links section below).

Related Links

• Blocking Queue github
• ThreadPool implementation in Java github

Simple PL/SQL code to throw NO_DATA_FOUND exception

Background

Good database question for beginners.Write a simple PL/SQL code snippet to throw NO_DATA_FOUND exception. You cannot raise this exception. Maybe try to understand how the candidate answers this. Simple code is as follows - 

DECLARE
   nowt VARCHAR(10);
BEGIN
   SELECT * INTO nowt FROM DUAL WHERE 1=0;
END;
/

and it should throw the exception - 

Error starting at line 8 in command:
DECLARE
   nowt VARCHAR(10);
BEGIN
   SELECT * INTO nowt FROM DUAL WHERE 1=0;
END;
Error report:
ORA-01403: no data found
ORA-06512: at line 4
01403. 00000 -  "no data found"
*Cause:    
*Action: 

Related Links

• Database Normalization(OSFG)
• Declare variables in PL/SQL(OSFG)
• Basic PL/SQL syntax and query executions on Oracle 11g R2 database(OSFG)
• Difference between DML and DDL statements in SQL(OSFG)
• Simple PL/SQL code to throw NO_DATA_FOUND exception 

Simple program to create deadlock between two threads and it's fix

Background

This is one of the very basic Java multithreading question - to write a simple java program to demonstrate a deadlock. So in this post I will provide code to demonstrate that - 

Java code to create deadlock between two threads

Code is as follows - 

/**
 * 
 * @author athakur
 * Simple deadlock program
 */
public class Deadlock {
    
    public static void main(String args[]) {
        
        final Object resourceOne = "res1";
        final Object resourceTwo = "res2";
        
        new Thread(new Runnable() {
            
            @Override
            public void run() {
                
                synchronized(resourceOne) {
                    System.out.println(Thread.currentThread().getName() + " accquired resource 1");
                    try {
                        Thread.sleep(2000);
                    } catch (InterruptedException e) {
                        // TODO Auto-generated catch block
                        e.printStackTrace();
                    }
                    synchronized(resourceTwo) {
                        System.out.println(Thread.currentThread().getName() + " accquired resource 2");
                    }
                }
            }
        }).start();
        
        new Thread(new Runnable() {
            
            @Override
            public void run() {
                synchronized(resourceTwo) {
                    try {
                        Thread.sleep(2000);
                    } catch (InterruptedException e) {
                        // TODO Auto-generated catch block
                        e.printStackTrace();
                    }
                    System.out.println(Thread.currentThread().getName() + " accquired resource 2");
                    synchronized(resourceOne) {
                        System.out.println(Thread.currentThread().getName() + " accquired resource 1");
                    }
                }
            }
        }).start();
        
    }

}

Copy above code in Deadloc.java file, compile and run it. You should see following output in console - 

Thread-0 accquired resource 1
Thread-1 accquired resource 2

And the program should hang.

Explanation

Thread 1 acquires lock over resource 1 and goes to sleep for 2 seconds. After sleep it would try to acquire lock on resource 2. When thread 1 was sleeping, thread 2 acquired lock over resource 2 and went to sleep for 2 seconds. After 2 seconds thread 2 would try to acquired lock on resource 1. Now it does not matter which thread wakes up. It will not be able to get lock on inner resource as other thread has acquired it and waiting for other to release. This will led to deadlock.

How to resolve this deadlock?

You can use Reentrant locks introduced in Java 1.5 to check if lock is available before locking it or you can do a timed lock (If lock is not available in x time move on). 

Another way to resolve this is to always have a fixed order to acquire lock. So both T1 and T2 threads will always lock resource 1 before trying to acquire lock on resource 2. This breaks the cycle that can lead to deadlock.

There is more more stupid way to prevent deadlock. When you are spawning new threads from main thread call join from main thread on all new threads before calling start() on next thread. Stupid? I know. It is same as single threaded application as you are executing threads sequentially. 

Couple of tips that may come handy -

• don't use multiple threads (like Swing does, for example, by mandating that everything is done in the EDT)
• don't hold several locks at once. If you do, always acquire the locks in the same order
• don't execute foreign code while holding a lock
• use interruptible locks

Related Links

• Race Condition, Synchronization, atomic operations and Volatile keyword(OSFG)
• ThreadLocal class in Java(OSFG)
• ReentrantLock in Java(OSFG) 
• How to avoid deadlock in Java Threads (java revisited)
• Tips to prevent deadlocks in java (SO)