gcc : Built-in functions for atomic memory access

這一篇是研究Memory barrier的心得。研究的原因是因為在UEFI環境下使用multi-processor protocol 來驗證CPU design，過程用到了相關的gcc Atomic函式。Atomic 提供同步機制，使得在Multi-Processor/Multi-Thread的系統下操作同一塊memory, 各個Core的Cache都能確保和Memory同步。

這邊只是以軟體thread寫個應用程式作範例來解釋Memory barrier, 如果不使用Built-in functions for atomic memory access而將__sync_fetch_and_add(&count,1);改成count++, 則count結果會不正確。

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>

static int count = 0;

void *MyTest(void *arg)
{
        for (int i=0; i<20000; ++i)         
            __sync_fetch_and_add(&count, 1);
        return NULL;
}

int main(int argc, const char *argv[])
{
        pthread_t Thread_Id[10];
        int i;

        for (i=0;i<10;++i)
                pthread_create(&Thread_Id[i], NULL, MyTest, NULL);
       
                // Wait until all threads have finished.
        for (i=0;i<10;++i)
                pthread_join(Thread_Id[i], NULL);
       
        printf("%d\n",count);
        return 0;
}

另外，__sync_synchronize (): This built-in function issues a full memory barrier.呼叫這個函式讓每個Core上的cache和memory同步。

<note> UEFI kernel提供EFI_MP_SERVICES_PROTOCOL，透過這個protocol,可以指定呼叫某個/或多個CORE (AP)分別執行特定的function，達到Multi-processing的效果。

-------------------------------------------------------------------------------------------------------------------------

Ps. 在windows下測試，需要自行加入pthread這個library。
如果你用Dev-C++ 5.11, 在Project->Parameters->Add library or object 加入

"../../Program Files/Dev-Cpp/MinGW64/x86_64-w64-mingw32/lib/libpthread.a"

順便解釋一下我認知的procces/thread:

process: 在系統中被註冊要執行的程式，其擁有CPU的使用權和獨立的位址空間。
thread: 系統處理工作的基本單位，一個CPU核心在同一時間只能提供一個thread來執行process
Multi-Thread: 將多個thread同時assign給一個process
Multi-Process: 每個process都分到thread來處理

UEFI : 在Linux(Ubuntu)下build UEFI Bios module

為什麼要在Linux(Ubuntu)底下build Bios module呢?
因為接手了大陸同事的UEFI Shell code，而他使用了 gcc 的library "Atomic Memory Access"，這個library在平常我們慣用的Visual Studio compiler下無法直接使用。

所以這兩天，花了點時間研究一下如何在Ubuntu下建構可以編譯的環境。
由於網路上比較少有這樣的文章分享, 因此特地新增一篇網誌做說明以及紀錄

基本上我是參考以下這兩篇Using EDK II with Native GCC、UDK2014 How to Build
，這邊解釋一下必要的流程

#取得EDK2 code base 請參考 https://github.com/tianocore/edk2

#安裝所需要的編譯工具
bash$:   sudo apt-get install build-essential subversion uuid-dev iasl

#取得nasm組譯器
bash$:   sudo apt-get install nasm

x86 architecture : Graphic UMA Frame buffer

傳統的顯卡控制方式是透過A/B Segment MMIO來輸出螢幕，但只有128K MMIO address, 顯然這樣的空間不夠用。現在的內顯都會在DRAM上"偷"一塊Memory做為輸出顯示用，系統上是看不到這塊Memory的，而這塊Memory稱為UMA frame buffer。一般在系統上看到系統顯示的記憶體遠小於所插的Dram記憶體，一大部分就是被frame buffer挖走的，至於frame buffer的size是可以在Bios選單去改變設定的。

UMA frame buffer之所以特殊是，他宣告為MMIO resource，但實際上decoder會將含有此address的cycle再forward給memory. 示意圖如下:

一般CPU bus的 traffic control 設計通常會先看這筆cycle是否往MMIO (C2P cycle)，若不是則再看是否往Memory (C2M cycle)，若都不是的話，則透過報錯機制回報錯誤(EBMC, MCA...)。

而外插式顯卡本身有自己的DRAM, 雖然都會要求MMIO resource, 但使用的是自己的記憶體。

Keyword: UMA( Unified Memory Architecture), Frame buffer, Graphic

g++ : libgcc_s_dw2-1.dll is missing

解決某些Windows平台在執行exe檔時，找不到libgcc_s_dw2-1.dll。缺少的這個dll應該是C++的library

我的g++版本(gcc -v): 4.8.1

解決方法就是在compile code 時加入 -static-libgcc  -static-libstdc++ 參數把所需要的library包進去

如下:

g++ -o main main.cpp 改成 

g++ -o main -static-libgcc  -static-libstdc++ main.cpp

使用DeviceIoControl::IOCTL_DISK_GET_LENGTH_INFO 獲取 Disk 大小

一般若要得到Sata硬碟或Usb硬碟Size，須要透過傳遞PASS_THROUGH參數來下Identify command，而參數須符合ATA command/ SCSI command spec, 使用上比較麻煩。

WinApi提供了一個比較通用的方式(IOCTL_DISK_GET_LENGTH_INFO)來得到，如下:

#include <windows.h>
#include <winioctl.h>
#include <stdio.h>

unsigned long long GetDiskLengthIoctl(const char *dsk)
{
  HANDLE hDisk = CreateFile( dsk,
                            GENERIC_READ,
                            FILE_SHARE_VALID_FLAGS,
                            0,
                            OPEN_EXISTING,
                            0,
                            0);
  if(hDisk == INVALID_HANDLE_VALUE)
    {
      printf("Could not open the disk. GetLastError() returned ", GetLastError());
      return 0;
    }
  GET_LENGTH_INFORMATION gli;
  DWORD ret;

  DeviceIoControl( hDisk,
                   IOCTL_DISK_GET_LENGTH_INFO,
                   0,
                   0,
                   &gli,
                   sizeof(gli),
                   &ret,
                   0);

  CloseHandle(hDisk);
  return gli.Length.QuadPart;
}
int main()
{

  const char *Disk = "\\\\.\\PhysicalDrive0"; // or \\\\.\\C:
  printf("size = %d (GB)\n", GetDiskLengthIoctl(Disk)/1024/1024/1024);
  printf("Lba = %x \n", GetDiskLengthIoctl(Disk)/512);

}

ATA : SATA-to-USB and SSD

由於USB的方便攜帶跟普及性，所以現在市售走USB protocol 的外接硬碟非常多，大部分的構造都是一顆SATA硬碟搭配SATA-to-USB  轉卡。還有些人是自行購買SATA-to-USB  轉卡透過USB port來外接硬碟 or SSD。接 SSD這樣的用法是有隱憂的，接下來解釋原因。

以上的架構(SATA過轉卡轉USB), 如果想傳原生的ATA Command給硬碟，則必須穿過  SATA-to-USB  轉卡才能將ATA command傳給碟機。方法是透過呼叫  DeviceIoControl 來發出  SCSI_PASS_THROUGH_DIRECT_WITH_BUFFER。以前在硬碟廠寫相關Utility (Update FW/ Identify...), 就是透過這個protocol發出ATA 給硬碟。

能夠在作業系統底下Access碟機，以硬碟廠的角度可以提供FAE做初期的檢測(看Smart table / 下一些Vendor Specific的command來判斷FTL/GC出了什麼樣的問題)當然還有最重要的update FW。

UEFI : 編譯文件

現有的Project要升級EDK2, 因此整理一下使用EDK2的經驗,並把所理解的做個簡單記錄:

首先，INF/DEC/DSC/FDF file是標準編譯UEFI code所需要準備的，在 AMI code裡DSC/FDF file是AutoGen出來的，而且因為AMI有自己的編譯介面，所以編譯AMI code還須要準備 "SDL", "CIF", "VEB"和 "ldl"檔。

以下介紹INF/DEC/DSC files

● 先定義名詞: $(Arch)  (對像是何種architecture)

Arch	Description
IA32	X86 32位CPU
X64	X86 64位CPU
IPF	Itanium Processor Family
ARM
EBC	EFI Byte Code

● $(MORDULE_TYPE)  (如SEC, PEI_CORE, PEIM, DXE_CORE,...)

UEFI : BuildOptions (Compiler Options)

用來access IO的變數若不宣告成volatile，但又怕因為最佳化而沒有實際access到IO的話，可以改Compiler Options 關掉最佳化編譯。更改UEFI 的Compiler Options， 可以選擇一次改全部 modules 或只改單一個 module，在EDK2都是透過修改DSC file。

1. 更改單一個 module 的 compiler options

[Components]

PackageNamePkg/NameOneDxe/NameOneDxe.inf {

    <BuildOptions>

    MSFT:*_*_*_CC_FLAGS = /Od

}

C# : from in where let select, 資料庫語法

public class Example_of_From_In_Let_Select
{
    public static void Main(string[] args)
    {
        string names = "Mr.Adam,Mrs.Eva,Mr.Henry,MS.May";
        var array = names.Split(',');
       
        var result = (
                from name in array
                where (name.Substring(0, name.IndexOf('.')) == "Mr" )
                let new_name = name + "<Male>"
                select new_name
            );
       
        foreach(string x in result)
            Console.WriteLine(x);
    }
}

/////// Output ///////

Mr.Adam<Male>

Mr.Henry<Male>

LeetCode : 169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.

// C++ Solution

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        if (nums.size() == 1) return nums[0];
        map <int, int> m;
        for (int i=0; i<nums.size(); i++) {
            if (m.find(nums[i]) == m.end() )
                m[nums[i]] = 1;
            else {
                m[nums[i]]++;
                if (m[nums[i]] > nums.size()/2)
                    return nums[i];
            }
        }
    }
};

UEFI : Event (事件)

UEFI 基本上是個單核/單工/提供Timer中斷的系統。<note 1>
但因為他提供了Timer中斷, 理論上就有機會做到異步操作以及分時多工。

實現這樣的目標可以透過 Boot Service提供的事件(Event)來達成。

首先使用 gBS->CreateEvent() 註冊一個 NotifyFunction (或稱CallBackFunction) 等待事件的發生或讓事件週期性的在背景執行。關閉Event須要呼叫  gBS->CloseEvent() 。因為是Boot Service所提供的，因此ExitBootServices()被系統呼叫後，BS的service/data都會消失。

先來看看Event的 typedef

AHCI: Index-Data Pair (IDP)

寫AHCI "Legacy" Option Rom的時候，為了要Access MMIO (AHCI Base Address) 得從 real mode 切換到Protect Mode 。但是AHCI其實有定義一種叫做Index Data Pair的機制，透過Access IO來替代MMIO。這種方法就可以在純real mode (<1MB) 底下寫AHCI Driver了

AHCI Spec第2.4章，定義了一個SATA Capability(0x12), 有這個Capability就是代表此AHCI有support Index Data Pair

這個Cap的結構如下

UEFI : Coding after S3 BootScript

做這個實驗的動機是工作上必須在S3 BootScript完成後加patch code, 當時趕時間就把程式直接加在AMI 的 code裡。趁現在有空，就研究看有沒有辦法把她加在公司package code裡。

想想，應該可以註冊個Notify CallBack function在Pei phase結束之前自動呼叫她，實驗結果是可以的。以下是我的作法，在S3 Pei init 的路徑上加上  

(*PeiServices)->NotifyPpi(PeiServices, mTest);

UEFI : SMM Kernel Code 重點整理: (一) Protocols

● 首先定義SMM driver和一般DXE driver:

DXE drivers

  regular DXE phase drivers that loads into system memory by DXE core driver.

SMM drivers  

  SMM Drivers are launched once, directly into SMRAM during SMM phase initialization.

SMM/DXE combined drivers

  Combination of drivers that loaded twice: as DXE driver and as SMM driver.

● 簡單介紹SMM Driver在做什麼

ATA : 硬碟密碼

在Bios底下常會看到兩種密碼可以設定, Bios密碼 / HDD(硬碟)密碼

這邊討論的是HDD 密碼, follow by ATA spec，首先，簡介如下

HDD User Password and HDD Master Password:

There are two levels of the HDD Password, the HDD User Password and the HDD master Password. If both levels of HDD Password have been registered, you can access the HDD by entering either of them.

以下兩個Identify table, 分別是設了ATA password (ATAIDSP.TXT)和未被設ATA password(ATAID.TXT) 時硬碟的identify傳回值

Hook my own interrupt vector in DOS

因為工作上需要驗證中斷的tool, 所以把塵封已久的Watcom DOS程式拿出來改。以下是一個基本的掛中斷、呼叫中斷、移除中斷的範例

// Author: Martin Lee  

 #include <stdio.h>
 #include <conio.h>
 #include <dos.h>

 #define getvect(n) _dos_getvect(n)

 #define setvect(n,v) {\
   _disable();\
   _dos_setvect(n,v);\
   _enable();\
 }

 #define HOOKVECTOR 0x7F

 int sig;

 void interrupt  (*origin_int)();

 void interrupt handle_7Fh(void)
 {
     sig=1;
     //_chain_intr( origin_int); // not execute original vector
 }

 void hook_int(void)
 {
     origin_int = getvect(HOOKVECTOR);
     setvect (HOOKVECTOR, handle_7Fh);
 }

 void restore_int(void)
 {
     setvect(HOOKVECTOR,origin_int);
 }

 void main()
 {
     sig = 0;

     hook_int();

     printf("Before int 7fh, sig = %d\n", sig);

     __asm  int 7Fh    
   
     printf("After int 7fh, sig = %d\n", sig);
       
     restore_int();
   
 }

----------------------執行結果-----------------------------

Before int 7fh, sig = 0

After int 7fh, sig = 1

C# : 測試程式執行的時間 (Time measurement)

using System.Diagnostics; // Stopwatch
using System.Threading; // Thread.Sleep

static void Main(string[] args)
{
    Stopwatch stopWatch = new Stopwatch();
    
    stopWatch.Start();
    Thread.Sleep(1000);
    stopWatch.Stop();

    // Get the elapsed time as a TimeSpan value.
    TimeSpan ts = stopWatch.Elapsed;

    // Format and display the TimeSpan value.
    string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:000}",
        ts.Hours, ts.Minutes, ts.Seconds, ts.Milliseconds);

    Console.WriteLine("RunTime " + elapsedTime);
    Console.ReadLine();
}

Reference:
https://msdn.microsoft.com/zh-tw/library/system.diagnostics.stopwatch(v=vs.110).aspx

C# : shuffling a given array

Shuffling a given array in C#

static Random _random = new Random();

static void Shuffle<T>(T[] array)
{
    int n = array.Length;
    for (int i = 0; i < n; i++)
    {
        // NextDouble Returns a random floating-point number that is greater than or equal to 0.0, and less than 1.0.
        int r = i + (int)(_random.NextDouble() * (n - i)); 
        T t = array[r];
        array[r] = array[i];
        array[i] = t;
    }
}

static void Main(string[] args)
{
    int[] array = new int [] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    Shuffle(array);
    foreach (int value in array)
    {
        Console.WriteLine(value);
    }
}