Thursday, September 29, 2016

Three Minutes Daily Vim Tip: Tab Completion

If you want to enable tab-completion feature in vim, just like terminal, here is what you can do.

$ echo "set wildmode=longest,list,full" >> ~/.vimrc
$ echo "set wildmenu" >> ~/.vimrc

Now, when you are opening a new file, use tab key to see the files in the folder:
:e <tab>

Thursday, September 22, 2016

Lazy Initialization Algorithm

This post presents my own understanding and analysis of lazy initialization algorithm explained in the book Elements of Programming Interviews, Chapter 6.

Say you are writing a program to manage memory and its initialization. When a user asks for a very large chunk of memory, say 1GB of size, and initialize all this big chuck of memory to some value, you are worried that it will take too long time to write out to the big block of memory address by address.

Is there any way to avoid brute-force initialization of the memory? Here is one way to avoid it and trick the user into believing as if the memory has been initialized without actually doing it.

1. If the user asks to read the value at specific address, you can first check whether that address has ever been written to since allocation of the memory (how? read on). If so, read the value at that address and return as requested. If not, don't even bother reading the value at that address---it will be just some garbage anyway as it is not initialized---and return what it should have been initialized to.

2. If the user asks to write some value at specific address, again check whether the address has been ever written to (how? read on). If so, just write out the value as requested to that address. If not, mark that location for "has been written" (how? read on) and write out the value as requested.

OK, you would agree that the scenario above makes sense, but there is one problem. How would you implement a method to mark which memory addresses have been written to?

The simplest method I can think of is to maintain a Boolean table for each address and mark, say 0 for not-written and 1 for written. Well, one problem with this method is that it requires initialization on its own, as you would have to start off with all-zero table, so it kind of defeats the whole purpose.

The second method is to store all the addresses where data have been written to in a hash table. The thing is that we do not know a priori the specific patterns of write addresses, so we may need to rehash often to spread out.

Finally, here is the alternative method to those mentioned above. I do not claim that this method is the best, as each implementation has its own pros and cons. I thought that this implementation is very clever that I should share.

Say the user asks for memory allocation for n elements with initialization. We then allocate (but not initialize) two more chunks of memory for n unsigned integers for indexes. The first will be called P, which will keep track of the number of indices thus far written to, which is maintained by a counter, say t. Another array will be called S, which will hold the index of write operation.

For each first-time write to index i, we write the counter value t into P[i] and write the index value i into S[P[i]], and increment the counter. To determine whether memory at index j has been written, first examine P[j] to see if it is between 0 to t-1. If so, it is likely that it has been written already. To verify with certainty, we double check to see if S[P[j]] is indeed j. If this holds, then it must be the case that this specific address has been already written. Otherwise, the address has not been written yet.

For better understanding, here is the actual code:


template <typename T>
class LazyArray {
private:
  unsigned size;
  T* A;
  unsigned *P;
  unsigned *S;
  unsigned t;
  T initVal;
  bool isWritten(unsigned idx) {
    if (P[idx] >= 0 && P[idx] < t)
      if (S[P[idx]] == idx)
        return true;
    return false;
  }

public:
  LazyArray(unsigned n, T initVal) {
    size = n;
    A = new T[n];
    P = new unsigned[2*n];
    S = &P[n];
    this->initVal = initVal;
    t = 0;
  }
  LazyArray(LazyArray &that) {
  }
  LazyArray& operator= (LazyArray& that) {
  }
  ~LazyArray() {
    delete[] A;
    delete[] P;
  }

  bool read(unsigned idx, T *pval) {
    if (idx<0 || idx>=size)
      return false;
    if (isWritten(idx))
      *pval = A[idx];
    else
      *pval = initVal;
    return true;
  }

  bool write(unsigned idx, T val) {
    if (idx<0 || idx>=size)
      return false;
    A[idx] = val;
    if (!isWritten(idx)) {
      P[idx] = t++;
      S[P[idx]] = idx;
    }
    return true;
  }

};


Russian Peasants Multiplication Algorithm

Here is a cool algorithm that calculates multiplication by addition and bit-shifting only. This method is exponentially faster than the literal implantation of multiplication in which x is added y times.



int multiply (unsigned x, unsigned y) {
  unsigned a,b;
  unsigned c = 0;
  // make sure a < b so that we add b a times
  if (x<y) {
    a = x;
    b = y;
  } else {
    a = y;
    b = x;
  }

  while (a > 0) {
    if (a & 1)
      c += b;
    a >>= 1;
    b <<= 1;
  }

  return c;
}

To prove that it works, consider the function
f(a,b,c) = ab + c
before the loop, during the loop, and after the loop.

Before the loop, we have
f = xy + 0 = xy

During the loop, we have for even a,
a' = a/2
b' = 2b
c' = c
f' = ab + c = xy

and for odd a,
a' = (a-1)/2
b' = 2b
c' = c + b
f' = ab + c = xy

Hence, it must be the case that f(a,b,c) = xy for any number of iterations in the loop by induction. Now, the ending condition of the loop yields a = 0, so it must be the case that
c = f - ab = f = xy

In other words, the return value is guaranteed to be the product of the input x and y!

Dutch National Flag Problem

Here is a very clever algorithm that I want to share. It is one solution to Dutch National Flag Problem, where an array of input is to be sorted into three partitions: one with those smaller than a given pivot, another one equal to the pivot, and the rest greater than the pivot.

For example, given input array 5 4 3 2 1 1 2 3 4 5 and pivot value, say 3, the output should be something like:
1 2 2 1 3 3 4 5 4 5

The following is the code:


// LIST: input array
// SIZE: # of elements in the array
// IDX: the index of the pivot
void dutchFlag (int *list, int size, int idx) {
  int pivot = list[idx];
  // The list will be partitioned into four as below:
  // bottom: [0, equal-1]
  // middle: [equal, current-1]
  // unclas: [current, large-1]
  // top   : [large, end]
  int equal, current, large;
  equal = current = 0;
  large = size;

  while (current < large) {
    int val = list[current];
    if (val < pivot) {
      swap(&list[equal], &list[current]);
      current++;
      equal++;
    } else if (val == pivot) {
      current++;
    } else {
      swap(&list[large-1], &list[current]);
      large--;
    }
  }
}

void swap (int *x, int *y) {
  int temp = *x;
  *x = *y;
  *y = temp;
}
Very cool!

Wednesday, September 21, 2016

Colorize GCC Output

To colorize GCC output, insert the following line into ~/.bashrc file:
export GCC_COLORS="error=01;31:warning=01;35:note=01;36:caret=01;32:locus=01:quote=01"

Now, load ~/.bashrc file and you are set!
$ . ~/.bashrc

For more info, refer here.

Tuesday, September 20, 2016

Binary Greatest Common Divisor Finder

While studying for coding interviews, I came up with a very neat example that I want to share with everyone. The question is to code a program that finds the greatest common divisor given two positive integers without invoking multiplication, division, and modulus operators.

The easiest way perhaps is to use Euclidean algorithm but that is just too slow. So, the following is a bit faster algorithm called binary GCD:

int binaryGCD(int a, int b) {
  if (a==b)
    return a;
  if (a==0)
    return b;
  if (b==0)
    return a;

  // divide a and b by 2 until they become both odd numbers
  int p2a, p2b;
  p2a = p2b = 0;
  while ((a&1) == 0) {
    p2a++;
    a >>= 1;
  }
  while ((b&1) == 0) {
    p2b++;
    b >>= 1;
  }
  int minpower = p2a < p2b ? p2a : p2b;

  if (a>b)
    return binaryGCD((a-b)>>1, b) << minpower;
  else
    return binaryGCD((b-a)>>1, a) << minpower;
}

The code above is my variant of binary gcd found in here. It is a bit harder to read but perhaps a bit faster though.

Three Minutes Daily Vim Tip: Indentation

Say you want to indent a block of code inside curly brackets. There are a couple of ways to do this. Before we run the commands, make sure to place your cursor inside the block of curly brackets.

>i{
>i}

The two commands above will indent the code inside the curly brackets. Specifically > indicates indentation, i indicates inside, and { or } indicates curly brackets.

You could of course make small manipulations, for example use < for de-indentation, and use any one of (){}[]<> after i for corresponding types of brackets/parenthesis.

Another way is to use vim's re-indentation feature, which will automatically adjust indentation by its own. Again, you will need to make sure to place the cursor within the block to run the following:

=i{

The first character = indicates re-indentation, and the rest should be identical to the previous context.

Finally, you may also re-indent the entire file by

gg=G

where gg places your cursor to the beginning of the file, and G indicates all the lines till the end of the file.

Sunday, September 18, 2016

How to Monitor CPU Temperature from OS X Terminal

You could of course install some Mac OS X apps that can do this, probably at some small fee or ads. Well, here is a much better and non-intrusive method for that, thanks to lavoiesl of github.

First, download osx-cpu-temp from github:
$ git clone https://github.com/lavoiesl/osx-cpu-temp.git

Compile, and install.
$ cd osx-cpu-temp
$ make
$ sudo make install

To run, simply run
$ osx-cpu-temp
55.2°C

That's it!

Friday, September 16, 2016

How to List Sizes of Directories or Folders in Linux

When you use
$ ls -lh
it only displays the sizes of files, but not the directories or folders.

Here is how to list the sizes of directories or folders:
$ du -sh *

Very handy!

Thursday, September 15, 2016

How to Open up Ports for Web Server with IPTABLES

I have a personal VPN server that I also want to setup as a web server. The VPN server is configured with iptables to drop all other connections, including TCP 80 (HTTP) and TCP 443 (HTTPS). So, here is how to open up those two ports.

Edit /etc/iptables.rules and insert two lines (green) as shown below:
...
*filter
:INPUT ACCEPT [0:0]
:FORWARD ACCEPT [0:0]
:OUTPUT ACCEPT [0:0]
-A INPUT -m conntrack --ctstate INVALID -j DROP
-A INPUT -m conntrack --ctstate RELATED,ESTABLISHED -j ACCEPT
-A INPUT -i lo -j ACCEPT
-A INPUT -d 127.0.0.0/8 -j REJECT
-A INPUT -p icmp -j ACCEPT
-A INPUT -p udp --dport 67:68 --sport 67:68 -j ACCEPT
-A INPUT -p tcp --dport 22 -j ACCEPT
-A INPUT -p udp -m multiport --dports 500,4500 -j ACCEPT
-A INPUT -p udp --dport 1701 -m policy --dir in --pol ipsec -j ACCEPT
-A INPUT -m state --state NEW -p tcp --dport 80 -j ACCEPT
-A INPUT -m state --state NEW -p tcp --dport 443 -j ACCEPT
-A INPUT -p udp --dport 1701 -j DROP
-A INPUT -j DROP
-A FORWARD -m conntrack --ctstate INVALID -j DROP
...

Your iptables.rules configuration is probably different from mine, but just make sure to add the two lines in green. Just make sure that these two lines should be inserted before the lines with DROP.

Next, reload the iptable
$ sudo iptables-restore < /etc/iptables.rules

That's it!

How to Extract Attachments from Gmail and Save to Files

This is a follow-up post from my previous post on how to retrieve messages from Gmail.

In order to save attached files, you just need to modify ~/.procmailrc file to read something like:
# First Recipe
:0HB
* ^(From).*(SOMEBODY)
* filename=
* ^Content-Disposition: attachment;
| munpack -q -C /WHERE/TO/SAVE

# Second Recipe
:0
/dev/null

The first recipe will filter out those mails from SOMEBODY with attachment(s) and save the file(s) to /WHERE/TO/SAVE folder. Make sure that you have mpack installed on the system:
$ sudo apt-get install -y mpack

The second recipe will simply discard all messages afterward. Therefore, nothing but the attachments will be saved locally.

Tuesday, September 13, 2016

How to Retrieve Emails from Gmail Periodically and Save as Files in Linux

In this tutorial, I will go over my own attempt to automate a process for fetching gmail and saving as files. This post is heavily based on the tutorial here with some modifications.

IMPORTANT:
In order for this to work, you will need to enable POP in Gmail setting.

You will also need to go to Google Account Security page and disable 2-step verification and turn on the option that allows less secure app.


First, install some necessary software:
$ sudo apt-get install -y fetchmail procmail openssl ca-certificates

Next, create ~/.fetchmailrc file and edit it with the following content
poll pop.gmail.com
with proto POP3
user "GMAIL_USERNAME@gmail.com"
there with password "YOUR_PASSWORD"
is "LINUX_USERNAME" here
mda "/usr/bin/procmail -f %F -d %T"
options
no keep
ssl
sslcertck
sslcertpath /etc/ssl/certs

Note that LINUX_USERNAME should be exactly what you would get from the following command:
$ echo $USER

Since your password is saved as a plain text, you will need to make sure to set read/write flags only for the owner:
$ chmod 600 ~/.fetchmailrc

Now, we need to configure procmail. Create ~/.procmailrc file and edit it with the following content:
# Environment variable assignments
PATH=/bin:/usr/bin:/usr/local/bin
VERBOSE=off                   # Turn on for verbose log
MAILDIR=$HOME/Mail            # Where Procmail recipes deliver
LOGFILE=$HOME/.procmaillog    # Keep a log for troubleshooting.
# Recipes
:0:
* ^(From).*(SOMEBODY)
$MAILDIR/SOMEBODY

This configuration will have procmail filter out any mails from SOMEBODY and save the message by appending to the file ~/Mail/SOMEBODY. Make sure to create the folder where it will be saved to:
$ mkdir ~/Mail

What about any other messages? They should be saved to path pointed by $MAIL, which we will need to specify. Edit ~/.bashrc to append the following line:
MAIL=/var/spool/mail/$USER && export MAIL

Let the change take effect immediately
$ source ~/.bashrc

Well, looks good. Let's test out. Run
$ fetchmail
2 messages for xxx@gmail.com at pop.gmail.com (3998 octets).
reading message xxx@gmail.com@gmail-pop.l.google.com:1 of 2 (3383 octets) flushed
reading message xxx@gmail.com@gmail-pop.l.google.com:2 of 2 (615 octets) flushed
You have new mail in /var/spool/mail/linuxnme

If your message is sent from SOMEBODY, it will be saved into ~/Mail/SOMEBODY file. If not, it will be saved to /var/spool/mail/$USER file. Open up these files and see if you are receiving the messages.

Finally, to schedule fetchmail every 5 minute, do the following:
$ crontab -e

Append the following line:
*/5 * * * * /usr/bin/fetchmail &> /dev/null

By the way, if you want fetching to run system-wise, edit /etc/crontab file instead.

Transition from Ubuntu to FreeBSD - sh, csh, bash

FreeBSD 10.3 comes with sh and csh in the base distribution. In fact, root's default shell is csh whereas a normal user default shell is sh.

It is possible to install bash by
# pkg install -y bash
...
======================================================================

bash requires fdescfs(5) mounted on /dev/fd

If you have not done it yet, please do the following:

mount -t fdescfs fdesc /dev/fd

To make it permanent, you need the following lines in /etc/fstab:

fdesc /dev/fd fdescfs rw 0 0

======================================================================

Because bash, derived from Linux world, may utilize fdescfs, some bash scripts may not properly run on FreeBSD unless it is mounted as mentioned above. For this reason, I decided not to stick with bash on FreeBSD, as learning BSD as BSD, not Linux, is the whole purpose.

However, I immediately changed root's default shell as sh, as I csh is just too different from bash. For instance, one needs to use setenv in place of export in csh.

To change default shell to sh, run
# chsh -s /bin/sh
and change the default shell from /bin/csh to /bin/sh

Note: do not change root's default shell as anything other than those included in the base distribution. Read here for more details.

Transition from Ubuntu to FreeBSD - root, su, sudo

In this series of posts, I will write my own attempt to transition from Linux (Ubuntu) to BSD (FreeBSD).

In Ubuntu, the security model is to invoke sudo command whenever root privilege is required. On the contrary, one needs to login as root using su - command. In fact, only those who are in the wheels group can login as root with su command.

A user not in wheels group cannot login as root:
$ su -
su: Sorry

To manually add a user, say unixnme, to wheels group, one needs to edit /etc/group to read something like
wheel:*:0:root,unixnme
...
operator:*:5:root,unixnme
...

Note that root is in the operator group as well. The operator group will have access to devices, so I might as well add to this group as well.

Now, the user can issue
$ su
or
$ su -
commands to login as root.

By the way, if one prefers the Ubuntu way with sudo command, it can be done.
Install sudo
# pkg install -y sudo

Add to sudoer by editing /usr/local/etc/sudoers to read something like
...
root ALL=(ALL) ALL
unixnme ALL=(ALL) ALL
...

That's it!

How to Compile From Sources with Debug Symbols

Say you want to debug vim. If you install vim using apt-get install command, it will install binary, which does not include debug symbol. Here is how to compile a program, for example vim, from source and compile with debug symbols.

First, un-comment lines that start with deb-src in /etc/apt/sources.list file.

Next, update the sources list
$ sudo apt-get update

Download source files
$ apt-get source vim
Note that I am issuing apt-get without sudo command.

Move to the vim directory and configure with -g option
$ cd vim_7.4.1689
$ ./configure CFLAGS='-g'

This -g option is important, as this will tell gcc to compile with debug symbols. If you need to tweak more options, run the following for help:
$ ./configure --help

Finally, make and install.
$ make -j4
$ sudo make install

How to Debug a Running Process Using GDB

Let's say you want to debug vim when run with sudo command, for example:
$ sudo vim /etc/fstab

It is easy to debug vim directly, but how would you do it when run with sudo? Well, here is one way to do it.

First, I will assume that you have vim executable file debug symbols. To find out how to compile vim with debug symbol, please refer to here. Say the file path is /usr/local/bin/vim.

Next, run the command that you want in one terminal:
$ sudo /usr/local/bin/vim /etc/fstab

Now, open up another terminal, and search for your vim process:
$ ps aux | grep vim
root     24687  0.0  0.0  63144  4212 pts/6    S+   19:04   0:00 sudo /usr/local/bin/vim /etc/fstab
root     24688  0.0  0.0  34180  5684 pts/6    S+   19:04   0:00 /usr/local/bin/vim /etc/fstab
linuxnme 24692  0.0  0.0  22572   988 pts/0    S+   19:04   0:00 grep --color=auto vim

We see two processes by root, one is sudo and the other is /usr/local/bin/vim, which is precisely what we want to debug, and its pid is 24668. To attach gdb to this process,
$ sudo gdb /usr/local/bin/vim 24688 -q
Reading symbols from /usr/local/bin/vim...done.
Attaching to program: /usr/local/bin/vim, process 24688
...
(gdb) 

Note that we are issuing sudo command before gdb here because we need superuser privilege to debug the process run by root.

Happy hacking!

Monday, September 12, 2016

How to Install DEB package with All Necessary Dependencies Automatically

When you are installing .deb packages with dpkg -i command, it does not automatically install necessary dependencies. For example, when I was trying to install Dropbox client on my freshly installed Ubuntu, I get
$ sudo dpkg -i dropbox_2015.10.28_amd64.deb 
Selecting previously unselected package dropbox.
(Reading database ... 211659 files and directories currently installed.)
Preparing to unpack dropbox_2015.10.28_amd64.deb ...
Unpacking dropbox (2015.10.28) ...
dpkg: dependency problems prevent configuration of dropbox:
 dropbox depends on python-gtk2 (>= 2.12); however:
  Package python-gtk2 is not installed.

dpkg: error processing package dropbox (--install):
 dependency problems - leaving unconfigured
Processing triggers for gnome-menus (3.13.3-6ubuntu3.1) ...
Processing triggers for desktop-file-utils (0.22-1ubuntu5) ...
Processing triggers for bamfdaemon (0.5.3~bzr0+16.04.20160701-0ubuntu1) ...
Rebuilding /usr/share/applications/bamf-2.index...
Processing triggers for mime-support (3.59ubuntu1) ...
Processing triggers for hicolor-icon-theme (0.15-0ubuntu1) ...
Processing triggers for man-db (2.7.5-1) ...
Errors were encountered while processing:
 dropbox

This is quite annoying. One solution is to remove Dropbox and install dependency first and re-install Dropbox. This process is outlined here for Google Chrome installation, but the same holds for any other .deb packages.

Well, it turns out that there is a good utility that will do this for you automatically. Try this!
$ sudo apt-get install -y gdebi
...
$ sudo gdebi dropbox_2015.10.28_amd64.deb Reading package lists... Done
Building dependency tree        
Reading state information... Done
Reading state information... Done
Requires the installation of the following packages: python-gtk2 

cloud synchronization engine - CLI and Nautilus extension
 Dropbox is a free service that lets you bring your photos, docs, and videos
 anywhere and share them easily.
 .
 This package provides a command-line tool and a Nautilus extension that
 integrates the Dropbox web service with your GNOME Desktop.
Do you want to install the software package? [y/N]:y
Fetched 0 B in 0s (0 B/s)                                            
Selecting previously unselected package python-gtk2.
(Reading database ... 218142 files and directories currently installed.)
Preparing to unpack .../python-gtk2_2.24.0-4ubuntu1_amd64.deb ...
Unpacking python-gtk2 (2.24.0-4ubuntu1) ...
Setting up python-gtk2 (2.24.0-4ubuntu1) ...
Selecting previously unselected package dropbox.
(Reading database ... 218162 files and directories currently installed.)
Preparing to unpack dropbox_2015.10.28_amd64.deb ...
Unpacking dropbox (2015.10.28) ...
Setting up dropbox (2015.10.28) ...
Please restart all running instances of Nautilus, or you will experience problems. i.e. nautilus --quit
Dropbox installation successfully completed! You can start Dropbox from your applications menu.
Processing triggers for gnome-menus (3.13.3-6ubuntu3.1) ...
Processing triggers for desktop-file-utils (0.22-1ubuntu5) ...
Processing triggers for bamfdaemon (0.5.3~bzr0+16.04.20160701-0ubuntu1) ...
Rebuilding /usr/share/applications/bamf-2.index...
Processing triggers for mime-support (3.59ubuntu1) ...
Processing triggers for hicolor-icon-theme (0.15-0ubuntu1) ...
Processing triggers for man-db (2.7.5-1) ...

Much easier, right?

Linux LVM Tutorial Part 1

Here is my scenario: I have two physical SSDs, one with 500GB and another with 250GB. I installed Ubuntu on 250GB disk using default LVM configuration. I am trying to add the disk with 500GB space into LVM.

First, let's check my configuration:
root@desktop:~# fdisk -l /dev/sd*
Disk /dev/sda: 465.8 GiB, 500107862016 bytes, 976773168 sectors
Units: sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk /dev/sdb: 232.9 GiB, 250059350016 bytes, 488397168 sectors
Units: sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 4096 bytes
I/O size (minimum/optimal): 4096 bytes / 4096 bytes
Disklabel type: gpt
Disk identifier: ...

Device       Start       End   Sectors   Size Type
/dev/sdb1     2048   1050623   1048576   512M EFI System
/dev/sdb2  1050624   2050047    999424   488M Linux filesystem
/dev/sdb3  2050048 488396799 486346752 231.9G Linux LVM
Disk /dev/sdb1: 512 MiB, 536870912 bytes, 1048576 sectors
Units: sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 4096 bytes
I/O size (minimum/optimal): 4096 bytes / 4096 bytes
Disklabel type: dos
Disk identifier: 0x00000000
Disk /dev/sdb2: 488 MiB, 511705088 bytes, 999424 sectors
Units: sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 4096 bytes
I/O size (minimum/optimal): 4096 bytes / 4096 bytes
Disk /dev/sdb3: 231.9 GiB, 249009537024 bytes, 486346752 sectors
Units: sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 4096 bytes
I/O size (minimum/optimal): 4096 bytes / 4096 bytes
fdisk: cannot open /dev/sdc: No medium found

As you can see, my 500GB drive is mapped to /dev/sda and 250GB drive is mapped to /dev/sdb with 3 partitions, the first being EFI system with 512MB of space, the second being Linux filesystem with 488MB, and the last being Linux LVM with 231.9GB of space. 

To allocate the entire 500GB drive to LVM, run
root@desktop:~# fdisk /dev/sda

Welcome to fdisk (util-linux 2.27.1).
Changes will remain in memory only, until you decide to write them.
Be careful before using the write command.

Device does not contain a recognized partition table.
Created a new DOS disklabel with disk identifier 0x55bec7d8.

Command (m for help): m

Help:

  DOS (MBR)
   a   toggle a bootable flag
   b   edit nested BSD disklabel
   c   toggle the dos compatibility flag

  Generic
   d   delete a partition
   F   list free unpartitioned space
   l   list known partition types
   n   add a new partition
   p   print the partition table
   t   change a partition type
   v   verify the partition table
   i   print information about a partition

  Misc
   m   print this menu
   u   change display/entry units
   x   extra functionality (experts only)

  Script
   I   load disk layout from sfdisk script file
   O   dump disk layout to sfdisk script file

  Save & Exit
   w   write table to disk and exit
   q   quit without saving changes

  Create a new label
   g   create a new empty GPT partition table
   G   create a new empty SGI (IRIX) partition table
   o   create a new empty DOS partition table
   s   create a new empty Sun partition table


Command (m for help): n
Partition type
   p   primary (0 primary, 0 extended, 4 free)
   e   extended (container for logical partitions)
Select (default p): p
Partition number (1-4, default 1): 
First sector (2048-976773167, default 2048): 
Last sector, +sectors or +size{K,M,G,T,P} (2048-976773167, default 976773167): 

Created a new partition 1 of type 'Linux' and of size 465.8 GiB.

Command (m for help): t
Selected partition 1
Partition type (type L to list all types): L

 0  Empty           24  NEC DOS         81  Minix / old Lin bf  Solaris        
 1  FAT12           27  Hidden NTFS Win 82  Linux swap / So c1  DRDOS/sec (FAT-
 2  XENIX root      39  Plan 9          83  Linux           c4  DRDOS/sec (FAT-
 3  XENIX usr       3c  PartitionMagic  84  OS/2 hidden or  c6  DRDOS/sec (FAT-
 4  FAT16 <32M      40  Venix 80286     85  Linux extended  c7  Syrinx         
 5  Extended        41  PPC PReP Boot   86  NTFS volume set da  Non-FS data    
 6  FAT16           42  SFS             87  NTFS volume set db  CP/M / CTOS / .
 7  HPFS/NTFS/exFAT 4d  QNX4.x          88  Linux plaintext de  Dell Utility   
 8  AIX             4e  QNX4.x 2nd part 8e  Linux LVM       df  BootIt         
 9  AIX bootable    4f  QNX4.x 3rd part 93  Amoeba          e1  DOS access     
 a  OS/2 Boot Manag 50  OnTrack DM      94  Amoeba BBT      e3  DOS R/O        
 b  W95 FAT32       51  OnTrack DM6 Aux 9f  BSD/OS          e4  SpeedStor      
 c  W95 FAT32 (LBA) 52  CP/M            a0  IBM Thinkpad hi ea  Rufus alignment
 e  W95 FAT16 (LBA) 53  OnTrack DM6 Aux a5  FreeBSD         eb  BeOS fs        
 f  W95 Ext'd (LBA) 54  OnTrackDM6      a6  OpenBSD         ee  GPT            
10  OPUS            55  EZ-Drive        a7  NeXTSTEP        ef  EFI (FAT-12/16/
11  Hidden FAT12    56  Golden Bow      a8  Darwin UFS      f0  Linux/PA-RISC b
12  Compaq diagnost 5c  Priam Edisk     a9  NetBSD          f1  SpeedStor      
14  Hidden FAT16 <3 61  SpeedStor       ab  Darwin boot     f4  SpeedStor      
16  Hidden FAT16    63  GNU HURD or Sys af  HFS / HFS+      f2  DOS secondary  
17  Hidden HPFS/NTF 64  Novell Netware  b7  BSDI fs         fb  VMware VMFS    
18  AST SmartSleep  65  Novell Netware  b8  BSDI swap       fc  VMware VMKCORE 
1b  Hidden W95 FAT3 70  DiskSecure Mult bb  Boot Wizard hid fd  Linux raid auto
1c  Hidden W95 FAT3 75  PC/IX           bc  Acronis FAT32 L fe  LANstep        
1e  Hidden W95 FAT1 80  Old Minix       be  Solaris boot    ff  BBT            
Partition type (type L to list all types): 8e
Changed type of partition 'Linux' to 'Linux LVM'.

Command (m for help): w
The partition table has been altered.
Calling ioctl() to re-read partition table.
Syncing disks.

Now, let's verify that /dev/sda has been formatted to type LVM:
root@desktop:~# fdisk -l /dev/sda
Disk /dev/sda: 465.8 GiB, 500107862016 bytes, 976773168 sectors
Units: sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disklabel type: dos
Disk identifier: ...

Device     Boot Start       End   Sectors   Size Id Type
/dev/sda1        2048 976773167 976771120 465.8G 8e Linux LVM

Perfect. Let's now add this physical drive to LVM physical volume:
root@desktop:~# pvcreate /dev/sda1
  Physical volume "/dev/sda1" successfully created

Again, let's verify:
root@desktop:~# pvdisplay 
  --- Physical volume ---
  PV Name               /dev/sdb3
  VG Name               ubuntu-vg
  PV Size               231.91 GiB / not usable 2.00 MiB
  Allocatable           yes 
  PE Size               4.00 MiB
  Total PE              59368
  Free PE               4075
  Allocated PE          55293
  PV UUID               ...
   
  "/dev/sda1" is a new physical volume of "465.76 GiB"
  --- NEW Physical volume ---
  PV Name               /dev/sda1
  VG Name               
  PV Size               465.76 GiB
  Allocatable           NO
  PE Size               0   
  Total PE              0
  Free PE               0
  Allocated PE          0
  PV UUID               ...

You can see that /dev/sdb3 is not fully allocated, as there is some free space. Let's examine logical volume:
root@desktop:~# lvdisplay
  --- Logical volume ---
  LV Path                /dev/ubuntu-vg/root
  LV Name                root
  VG Name                ubuntu-vg
  LV UUID                ...
  LV Write Access        read/write
  LV Creation host, time ubuntu, 2016-09-12 21:40:26 +0900
  LV Status              available
  # open                 1
  LV Size                215.99 GiB
  Current LE             55293
  Segments               1
  Allocation             inherit
  Read ahead sectors     auto
  - currently set to     256
  Block device           252:0

As you can see, there is only one logical volume, namely /dev/ubuntu-vg/root and its space is only 216GB out of total 232GB of /dev/sdb3. To enlare the volume of this logical volume, I run
root@desktop:~# lvextend /dev/ubuntu-vg/root /dev/sdb3
  Size of logical volume ubuntu-vg/root changed from 215.99 GiB (55293 extents) to 231.91 GiB (59368 extents).
  Logical volume root successfully resized.

Let's verify:
root@desktop:~# lvdisplay
  --- Logical volume ---
  LV Path                /dev/ubuntu-vg/root
  LV Name                root
  VG Name                ubuntu-vg
  LV UUID                ...
  LV Write Access        read/write
  LV Creation host, time ubuntu, 2016-09-12 21:40:26 +0900
  LV Status              available
  # open                 1
  LV Size                231.91 GiB
  Current LE             59368
  Segments               1
  Allocation             inherit
  Read ahead sectors     auto
  - currently set to     256
  Block device           252:0

Viola! I have enlarged the logical volume /dev/ubuntu-vg/root to use the entire /dev/sdb3 space.

Next, I will create three logical volumes from group volume home:
root@desktop:~# lvcreate --name vm --size 100GB home 
  Logical volume "vm" created.
root@desktop:~# lvcreate --name home --size 200GB home
  Logical volume "home" created.
root@desktop:~# lvcreate --name backup -l 100%FREE home
  Logical volume "backup" created.

The first command creates logical volume named vm with size 100GB from volume group home.
The second command creates logical volume named home with size 200GB from volume group home.
The third last command creates logical volume named backup with the remaining space of group volume home.

After all these steps, my final logical volume info is given below:
root@desktop:~# lvdisplay 
  --- Logical volume ---
  LV Path                /dev/ubuntu-vg/root
  LV Name                root
  VG Name                ubuntu-vg
  LV UUID                ...
  LV Write Access        read/write
  LV Creation host, time ubuntu, 2016-09-12 21:40:26 +0900
  LV Status              available
  # open                 1
  LV Size                231.91 GiB
  Current LE             59368
  Segments               1
  Allocation             inherit
  Read ahead sectors     auto
  - currently set to     256
  Block device           252:0
   
  --- Logical volume ---
  LV Path                /dev/home/vm
  LV Name                vm
  VG Name                home
  LV UUID                ...
  LV Write Access        read/write
  LV Creation host, time desktop, 2016-09-12 23:14:54 +0900
  LV Status              available
  # open                 0
  LV Size                100.00 GiB
  Current LE             25600
  Segments               1
  Allocation             inherit
  Read ahead sectors     auto
  - currently set to     256
  Block device           252:1
   
  --- Logical volume ---
  LV Path                /dev/home/home
  LV Name                home
  VG Name                home
  LV UUID                ...
  LV Write Access        read/write
  LV Creation host, time desktop, 2016-09-12 23:15:11 +0900
  LV Status              available
  # open                 0
  LV Size                200.00 GiB
  Current LE             51200
  Segments               1
  Allocation             inherit
  Read ahead sectors     auto
  - currently set to     256
  Block device           252:2
   
  --- Logical volume ---
  LV Path                /dev/home/backup
  LV Name                backup
  VG Name                home
  LV UUID                ...
  LV Write Access        read/write
  LV Creation host, time desktop, 2016-09-12 23:16:11 +0900
  LV Status              available
  # open                 0
  LV Size                165.76 GiB
  Current LE             42434
  Segments               1
  Allocation             inherit
  Read ahead sectors     auto
  - currently set to     256
  Block device           252:3


For Linux system to take effect on resize of the partition, you will need to run the following:
root@desktop:~# resize2fs logical_volume_path

where logical_volume_path is /dev/home/home or /dev/ubuntu-vg/root, etc.