Basics Of LDAP … Part 1

LDAP is a set of rules that computers and networked devices can adhere to access common information over a network. For example, classic case can be  employee-information which might be stored in a directory so that people and applications can locate their contact information. Such contact information might include email addresses and fax numbers, or even additional data that unambiguously identifies employees’ attempts to access enterprise applications.

Thus we can say that a directory is simply a collection of information (mind that information is meaningful collection of data).

Computer applications often have their own directories. For example, we can store usernames and passwords in a data file, which is thus a directory of users.

LDAP – Light Weight Directory Access Protocol was developed in early 1990s as directory protocol. LDAP provides client-server access to directories over a computer network and is therefore a directory service. In addition to offering the ability to search and read information, it defines a way to add, update, and delete information in a directory.

LDAP Structure can be understood by dividing into,

– Information model
– Naming model
– Functional model

Information model defines what kind of information can be stored in directory and how that information is structured. Data in LDAP is organised in a hierarchical tree. Each node in this tree is called an ENTRY and first entry is called ROOT. An entry is a named collection of attributes, which have type and value.
Example: objectclass = person requires sn (surname), cn (common name) and allows a list of other attributes.

An entry can be located in LDAP by specifying either the distinguished name (dn) or the relative distinguished name (rdn). The dn is the full LDAP tree path whereas the rdn is just a unique identifier for a specific entry in the tree.

Naming model defines how information is organized and referenced. Like domain names, the name of any entry should be unique across all LDAP servers.  Position of entry in a hierarchy given by it’s distinguished name (DN). Each component of a DN is called a relative distinguished name (RDN).

Functional model defines how directory information is retrieved and modified. It supports authentication (bind , unbind), search, and updates (add, Delete, modify).

Continued to Part 2 … Happy Learning !!!

Spring AOP

Question: What is AOP ?

It is modularisation of cross cutting concerns. Non business code which is scattered through out the application is modularised into an entity called as

Aspect in this approach. Non business code is of importance for many things like logging point of view, authorisation, autthentication etc.

Question: What is Advise, Joinpoint, Pointcut, and Aspect ?

In simple terms

Advise – What you want to do at some execution point (Joinpoint) in your application.

Jointpoint –  execution point in your program where you want advice to run. This could be method invocation, exception being thrown, or field being modified.

POintcut – a language construct rather, matches one or more joinpoints where advise will be plugged in. Regular expresions are commonly used to define pointcuts.

Aspect – An entity which has Pointcut + Advice.

Question: What are different type of advices ?

Around advice: Advice that surrounds a joinpoint such as a method invocation. This is the most powerful kind of advice. Around advices will perform custom behavior before and after the method invocation. They are responsible for choosing whether to proceed to the joinpoint or to shortcut executing by returning their own return value or throwing an exception.
This is implemented by the use of MethodInterceptor interface which is defined by AOP alliance. Other interfaces for all other advices are part of spring framework.

Before advice: Advice that executes before a joinpoint, but which does not have the ability to prevent execution flow proceeding to the joinpoint (unless it throws an exception).
This is implemented by the use of MethodBeforeAdvice interface

Throws advice: Advice to be executed if a method throws an exception. Spring provides strongly typed throws advice, so you can write code that catches the exception (and subclasses) you’re interested in, without needing to cast from Throwable or Exception.

This is implemented by the use of ThrowsAdvice interface

After returning advice: Advice to be executed after a joinpoint completes normally: for example, if a method returns without throwing an exception.

Question : You want some advice to be executed during execution of constructor of some bean. How to achieve it in Spring?

Spring only supports method joinpoints, and not constructor or field joinpoints.

Question: What is weaving ?

Process to apply aspects to target objects. This is achieved in spring at runtime by wrapping these objects with proxies. Proxy handles method calls, does

some aspect logic and then finally invokes the target method.

Question: Class MyBean

{

String abc;

private myMethod1(){…}

final public myMethod2(){…}

public myMethod3() {…}
}

Suppose you want the method of the above bean to be advised. What are the potential problems which you may face ?

In case spring uses CGLIB – Code Generation library, it will create subclass to your class. But final and private methods can not be overriden, so they can

not be advised. Methods are overridden and adice in woven in them.

Question: Schema-based AOP support ?

<aop:config>
<aop:aspect id=”myAspect” ref=”aBean”>
…

<aop:before pointcut=”execution(* com.ask.*.*(..))” method=”doCheck”/>

<aop:after-returning
pointcut-ref=”refToPointcutDefinedEarlier”
returning=”retVal”
method=”doCheck”/>   <!– returning=”retVal”  to capture the value returned from function–>

</aop:aspect>
</aop:config>

<bean id=”aBean”>
…
</bean>

Around advice

public Object doSomething(ProceedingJoinPoint pjp) throws Throwable {
// some work
Object retVal = pjp.proceed();
// somework
return retVal;
}

Question:  What happens when multiple pieces of advice all want to run at the same join point?

When two pieces of advice defined in different aspects both need to run at the same join point, unless you specify otherwise the order of execution isundefined. You can control the order of execution by specifying precedence. This is done in the normal Spring way by either implementing the org.springframework.core.Ordered  interface in the aspect class or annotating it with the Order annotation. Given two aspects, the aspect returning the lower value from Ordered.getValue() (or the annotation value) has the higher precedence.

When two pieces of advice defined in the same aspect both need to run at the same join point, the ordering is undefined (since there is no way to retrieve the declaration order via reflection for javac-compiled classes).

Class Loading In Java/J2EE

Class Loaders are a powerful mechanism for dynamically loading software components ie a class on the java platform. Lets us see an example below.

————————————————
Class C
{

D d  = new D();

}
———————————————–
There are two important things worth for our attention. First, assuming the class loader L loads the class C, then jvm will use the same class loader to load the class referenced by C. Before, the JVM allocates the object of class D, it must first resolve the symbolic reference of D. Other point is that ‘Delegation’ model is followed for class loading. A class loader can ask another class loader to load class on its behalf and a class type is uniquely determined by ‘Class Name with package + Loader’.

Each class object contains a reference to its defining loader and each loader refers to all the classes it defines. Classes are un-loaded when their defining  loader is garbage collected.

Regular Java applications running from command line involve three classloaders – Bootstrap, Extensions and System-Classpath classloaders.

– Bootstrap classloader is the parent of all classloaders and loads the standard JDK classes in lib directory of JRE (rt.jar).

– Extensions Classloader is the immediate child of Bootstrap classloader. This classloader loads the classes in lib/ext directory of the JRE or java.ext.dirs system property.

– System-Classpath classloader is the immediate child of Extensions classloader. It loads the classes and jars specified by the CLASSPATH environment variable, java.class.path system property, -cp or –classpath command line settings. If any of the jars specified in one of the above manner have a MANIFEST.MF file with a Class-Path attribute, the jars specified by the Class-Path attribute are also loaded.

It is therefore following points must be taken into consideration while writing custom class loaders.

– subclass of java.lang.ClassLoader
– implement loadClass()
– check if the class requested is already loaded, or check if a system class
– Define class for VM and resolve it.
– Return the class to caller.

J2EE class loader hierarchy:

In J2EE, each application is packaged as an Enterprise ARchive (EAR). The EAR is a self-contained deployment unit having minimal dependencies on external classes (with the exception of application server classes).  Each EAR gets its own classloader.

Let us start with the structure of EAR,an EAR file may contain following components.

– application.xml – XML file describing the contents of the EAR.

– EJB-JAR – Each EJB-JAR can contain one or more EJBs

– WAR – Each WAR contains exactly one web application.

– Dependency JAR – Normal JAR file containing classes that are shared between web and ejb application. It can also be a third party library used by both web and ejb application.

The following figure below clarifies class loading hierarchy,

FIGURE:

Some points to note,

1. The A.jar and B.jar are located within the same EAR containing the EJB-JAR. The EAR classloader loads them, but they become visible to the EJB classloader (a child of EAR classloader), when the EJB-JAR references these jars in its manifest file.

2.All of the WAR classloaders however inherit from the same parent viz. EJB classloader. The rationale behind this hierarchy is that EJBs contain the core of the business logic and web applications have to “see” them to invoke their business methods. Of course to “see” them the WAR manifest file has to have an entry as shown earlier.

We will see how configurations can be done in server and what are the parameters available for customizing class loading policies.

Happy Learning !!!

Serialization VS Externalisation

Serialization is all about saving the state of the object. You can easily serialize any object if it implements the Serializable interface. This interface does not contain any methods, so it’s just a sign for the compiler and the Java Virtual Machine (JVM) that this class is serializable.

In order to serialize an object, you need the output stream OutputStream, which must be put into the special serialization stream called ObjectOutputStream. After that, you only need to call the method writeObject() to serialize the object and send it to the output stream. In order to deserialize an object, you need to convert InputStream into ObjectInputStream and then call the readObject() method. As usual, you will get a reference to an Object type, so you’ll also need to make a class cast to get an object of required type.

But there are times when you have special consideration for the serialization of an object. For example, you may have some security-sensitive parts of the object, like passwords, which you do not want to keep and transfer somewhere. Or, it may be worthless to save a particular object referenced from the main object because its value will become worthless after restoring.

If you implement Serializable interface, you will mark the fields as transient but you can have better control over serialisation by use of Externalizable.
This interface extends the original Serializable interface and adds writeExternal() and readExternal(). These two methods will automatically be called in your object’s serialization and deserialization, allowing you to control the whole process.

There is one major difference between serialization and externalization: When you serialize an Externalizable object, a default constructor will be called automatically; only after that will the readExternal() method be called.

————————————————————————-

package com.ask;

import java.io.Externalizable;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectInputStream;
import java.io.ObjectOutput;
import java.io.ObjectOutputStream;

class Test implements Externalizable {

int i;
String s;

public Test() {
System.out.println(“Test default constructor”);
}

public Test(String x, int a) {
System.out.println(“Second constructor”);
s = x; i = a;
}

public String toString() {
return s + i;
}

public void writeExternal(ObjectOutput out)
throws IOException {

System.out.println(“In write external”);
out.writeObject(s);
out.writeInt(i);
}

public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException {

System.out.println(“In *read* external”);
s = (String)in.readObject();
i = in.readInt();
}

public static void main(String[] args)
throws IOException, ClassNotFoundException {

// Create the object
Test d = new Test(“String value”,1514);
System.out.println(d);

//Serialize
ObjectOutputStream o = new ObjectOutputStream(
new FileOutputStream(“test.out”));

o.writeObject(d);

o.close();

//        Now deserialize
ObjectInputStream in = new ObjectInputStream(
new FileInputStream(“test.out”));
d = (Test)in.readObject();

System.out.println(d);
}
}

 

Output  :

Second constructor
String value1514
In write external
Test default constructor
In *read* external
String value1514

 

————————————————————————-

Performance Consideration – Use Externalization as recommended.

Happy Learning !!!

Spring Drill One …

 

1. Suppose there is a singleton bean which has dependency on some session specific bean. What things will you do while injection of this bean ?

2. What are three approaches to write AOP code in Spring ?

3. It is required that Aspect should be created by AspectJ runtime in your application. How will you ahieve this?

4. You want some advice to be executed during execution of constructor of some bean. How to achieve it in Spring?

5. Class MyBean

  {

               String abc;
   
               private myMethod1(){…}

                final public myMethod2(){…}

                public myMethod3() {…}
  }

Suppose you want the method of the above bean to be advised. What are the potential problems which you may face ?
6. What if user proxies a singleton bean ?

7. If in a servlet based application, user uses global-session scope, what is going to happen?

8. What are commonly used implementations of Application Context ?

9. What is the use of ProxyFactoryBean ?

10. Explain lifecycle of a bean.

Inside Generational Garbage Collection Mechanism in Java…

Java garbage collection mechanism provides an automatic solution to memory management. In most cases it frees us from manual taskof adding any memory management logic to our applications. The limitation of this approach is that we can not really enforce when it should run or when it should not. The JVM decides when to run the garbage collector. However from within our program, we can ask JVM to run garbage collector but there is no guarantee. JVM will typically run the garbage collector, when it senses the memory is running out. For sure, it runs garbage collector before giving OutOfMemoryException.

Looking at the history, there are many garbage collection algorithms available like copying collectors, mark sweep collector, mark compaction collectors etc. The 1.0 and 1.1 JDKs make use of mark sweep collector. Techniques used by 1.2 and later JVMs are known as Generational Garbage Collection Techniques. This makes use of several garbage collection algorithms as per suitability. In simple words, a kind of Hybrid approach.

In generational garbage collection mechanism, heap is divided into multiple partitions called as Generations. These generations are named as Young generations and Older generations. The objects are created in young generation and objects that meet some promotional criteria like to have survived a certain garbage collection cycles are then promoted to next older generation.

A generational collector is free to use a different collection technique for different generation and perform garbage collection  separately. The choice of GC algorithm is such that the optimal performance is achieved. For young generation, JVM may make use of copying collector and for older generations, it may use mark compaction.

There are several advantages of this generational GC mechanism. It does not garbage collect all the generations at once. It first triggers a Minor collection which garbage collects younger generations. A Major collection on the other haand will collect both younger and older generations. So, it is worth to remeber that whenever we request garbage collection with System.gc() from our code, it is just a request but it is for sure if this request is accepted, JVM triggers Major collection and hence it is not advisable to request GC from our code.

Complexity Analysis Of Algorithms – Part 2…

Question 1.  Show that 5x²   is O(x³).

5x²   < = C x³  ,  for C = 5 and for all values of x >= 1, the inequality holds. So it is proved that is O(x³).

Question 2. Calculate the time complexity of Binary Search algorithm.

In Binary Search, approach is to divide the sorted list into two parts, then compare if the element to be searched is in upper half or lower half. After this comparison, the process to either divide the upper half or lower half into two parts continues till we get the list with single element. Here search stops.

 Let us assume a list with n elements:  a1, a2, a3 … an

Now each pass, divides the list in to two parts,

 After first pass, n/2 .  After second pass, n/2²  …. So on and so far till size is reduced to 1.

                                    n/2, n/2²  , n/2³, n/2⁴, …,  n/2^k    

Hence, our search will stop when n/2^k  = 1 , log n = k.  It is therefore proved that time complexity of binary search is O(log n).

Question 3. Calculate the complexity to delete the first node and last node of the linked list.

The complexity is constant and is of order O(1). It is clear that deletion of first node will not at all depend on the size of the list. Last node deletion will be of order O(n).

Question 4. Claculate the time complexity of the code snippet given below.

1.         for (int i=0; i<N; i++)

2.                       for (int j=i+1; j<N; j++)

3.                             if (A[i] > A[j])

4.                                  swap( A[i], A[j] );

Step 1. is executed N times as it is simple loop for N times.

Step 2. is executed N-1 for first pass, N-2 for second pass and so on.

Thus, N-1 + N-2 + N-3 + … + 1 = N(N-1)/2

Step 3. is executed N(N-1)/2 same as step 2.

 Step 4. is executed at the maximum N(N-1)/2 each which is equal to the number of times the inner loop is executed.

Hence calculating worst case,

= N + N(N-1)/2 + N(N-1)/2 + N(N-1)/2

= N + 3 N(N-1)/2

= Quadratic Equation,

So we can say O(n²)

 
HAPPY LEARNING ...

 

Complexity Analysis Of Algorithms

Why is it necessary to study the complexity of algorithms?

 The time required to solve a problem is of utmost important for using any algorithm. So it is necessary to study the behavior of this time when size of input to the algorithm is increased. It is important to know the number of operations taken by an algorithm to produce the output.

 Big – O notation is one of the measures to estimate the number of operations an algorithm uses as input grows.

This Big – O notation was introduced by a German mathematician Paul Gustav Bachmann.

This is defined as,

 f(x) is O(g(x)) if C and K are constants such that | f(x)| <= |g(x)| whenever x >K

  C and K are called the witness to this relationship.

 Let us understand some examples

What is O(1) ?

This comes in to picture when number of operations to solve a problem does not depend on the size of the input. For example, time to give movie ticket to the first in the queue, time to remove an element from the stack and so on.

What is O(n) ?

When number of operations to solve a problem varies proportionally to the size of input then algorithm is said to have linear complexity. The linear search to find out a number from the list, if you double the size of list, number of operations also gets doubled.

What is O(n^2) ?  [Read as n raised to power 2]

Quadratic complexity, when you double the input, number of operations increases in the order of square of increase.

For example in bubble sort, worst case complexity comes O(n^2).

For instance, list to be sorted is 5 4 3 2 1. We can see that

–          first pass requires n-1 operations

–          second pass requires n-2 operations

–          third pass requires n-3 operations and so on till 1

So, (n-1) + (n-2) + … + 1 = Quadratic equation  =>   O(n^2)

* In any quadratic expression, the significant contribution is made by squared term, so we can easily ignore linear terms

Similarly, we have logarithmic complexiy O(log n) for Binary Search. This can also be easily established.

 HAPPY LEARNING !!!

Type safe stack implementation and its use to reverse a string …

/* Type safe stack implementation and its use to reverse a string.

 * However this implementation is not thread safe. Suggestion for

 * optimization are most welcome*/

package mypackage;

 class Node<T>

{

            T data;

            Node<T>  next;

            Node(T data, Node<T> next)

            {

                        this.data = data;

                        this.next = next;

            }

}

public class MyStackImplementation <T>{

            private Node<T>  top;

            MyStackImplementation()

            {

                         top = null;

            }

public static void main(String args[])

{

                        MyStackImplementation<Character> mystack = new MyStackImplementation<Character>();

                        String str1 = new String(“My Name is Anthony … “);

                        char[] array = str1.toCharArray();

                        // insert  elements to the stack

                        for(int i = 0; i < array.length; i++)

                                    mystack.push(array[i]);

                        char[] reversedArray = new char[array.length];

                        for(int i = 0; i < array.length; i++)

                                    reversedArray[i] = mystack.pop();

                        System.out.println(“elements in reverse order : “+ new String(reversedArray));

}

           // Funtion to check if the stack is empty

            public boolean isEmpty() {

                        if(top == null)

                                    return true;

                        else

                                    return false;

            }

  // Read the top element but does not remove it.

            public T peek() {

                                   if(!isEmpty())

                        {

                        return top.data;

                        }

                        else

                                    return null;

            }

// Remove the top element 

            public T pop() {

                        T temp = null;

                        if(!isEmpty())

                        {

                         temp = top.data;

                         top = top.next;

                        }

                        return temp;

            }

// To push an element on stack

            public void push(T obj) {

                        top = new Node<T>(obj,top);

            }

}

Use of Volatile in C and Java …

The “volatile” keyword is used not only in Java but in C, C++ also. Let us start with its use in C.

The motivating factor for its use is when a variable is subjected to changes from outside the program. The shared data can be modified in signal handlers or interrupt service routines.

By looking at the program, one can not predict if this variable is being changed and this is the trap for the compiler while doing code optimization. When compiler sees that this variable is not being changed, it may apply optimization on it and as a result the value may get cached in registers. When external factors change the original value, your thread of control might be using the old cached value.

Let us see how it happens, in the code below

————————————————————————————

int global_flag = FALSE;

void main()
{
…
 while (!global_flag)
 {
  // some code
 }
…
}
————————————————————————————-

Here, global_flag is soe variable which may be changed by some ISR. But when compiler optimizes this code, it finds that !global_flag is always TRUE, so it takes it out of the loop and generates optimised code as shown below leading to

————————————————————————————

int global_flag = FALSE;

void main()
{
…
 while (TRUE)
 {
  // some code
 }
…
}
————————————————————————————

It is therefore,when variables are declared as volatile , they are not used in  optimizations by the compiler because their values can change at any time. The system always reads the current value (not the cahced value) of a volatile variable at the point it is requested, even if a previous instruction asked for a value from the same object. Also, the value of the object is written immediately on assignment.

To be specific, the change in value may happen in these scenarios

Type 1.  Memory-mapped peripheral registers.
Type 2.  Global variables modified by an ISR (interrupt service routine)
Type 3.  Global variables within a multi-threaded application.
Now let us take a deep Dive in Java for volatile,

In case of Java, motivation for use of volatile is more of  type 3  where a multi-threaded application comes into picture and multiple threads accesing the shared data.

Java specification says, each thread has a working memory, in which it may keep copies of the values of variables from the main memory that is shared between all threads. To access a shared variable, a thread usually first obtains a lock and flushes its working memory. This guarantees that shared values will thereafter be loaded from the shared main memory to the threads working memory. When a thread unlocks a lock it guarantees the values it holds in its working memory will be written back to the main memory.

There are certain rules as per Java Language Specifications which are obeyed when we define any variable as volatile. (Please refer http://java.sun.com/docs/books/jls/third_edition/html/j3TOC.html)

Let T be a thread and V be a variable. There are certain constraints on the actions performed by T with respect to V.

Following are the actions, 
–  By use, we mean – transfer the contents of the thread’s working copy of a variable to the thread’s execution engine.
– By assign, we mean – transfer a value from the thread’s execution engine into the thread’s working copy of a variable.
– A read action (by the main memory) transmits the contents of the master copy of a variable to a thread’s working memory for use by a later load action. 
– A load action (by a thread) puts a value transmitted from main memory by a read action into the thread’s working copy of a variable.
– A store action (by a thread) transmits the contents of the thread’s working copy of a variable to main memory for use by a later write action.
– A write action (by the main memory) puts a value transmitted from the thread’s working memory by a store action into the master copy of a variable in main memory.

.
JLS impoed rules on these actions are,

– An use or assign by T of V is permitted only when dictated by execution by T of the program according to the Java programming language’s execution model.
– A store action by T on V must intervene between an assign by T of V and a subsequent load by T of V. (a thread is not permitted to lose its most recent assign.)
– An assign action by T on V must intervene between a load or store by T of V and a subsequent store by T of V. (Less formally: a thread is not permitted to write data from its working memory back to main memory for no reason.) 
–  After a thread is created, it must perform an assign or load action on a variable before performing a use or store action on that variable. (Less formally: a new thread starts with an empty working memory.) 
–  After a variable is created, every thread must perform an assign or load action on that variable before performing a use or store action on that variable. (Less formally: a new variable is created only in main memory and is not initially in any thread’s working memory.)