0%

314 Binary Tree Vertical Order Traversal

原題目是付費題目,有興趣看到完整的請自行付費觀賞,在此就不提供超連結了。

Introduction

  • 給定一個 binary tree,將此 tree 以 vertical 的方式走過,
  • 輸出時,從最左邊開始輸出
  • 相同 colume 的算同一個 group,若屬於同 row 且同 colume,則從左邊開始算起

    Read more »

還記得以前在工三讀書時,常常看到 Chun Norris 坐在我前面,然後畫面上是一張一張的卡片在不停地翻動,每張卡片上面都標記者一個日文單字, 看他快速地翻閱這些卡片,感覺就是在背頌單字,那時候也就沒有去想太多了。

沒想到過了幾年後,Chun Norris 竟然出書了!!!

英、日語同步Anki自學法:我是靠此神器,最短時間通過日檢N1、多益975分

看到這個消息後,就馬上預購了一本這個書,不但捧朋友的場,同時也順便瞭解看看到底 Anki 是什麼樣的東西。

Read more »

最近因為在處理 firefox 的憑證問題,所以要藉由 mozilla 自己的 certutil.exe來進行憑證的操作,
由於Mozilla現在已經不在官網提供執行檔,必須要自己手動下載來Build,因此就到官網來查詢安裝步驟了

Read more »

之前在網路上看到了一篇 paper
mTCP: A Highly Scalable User-level TCP Stack for Multicore Systems
標題覺得還滿有趣的,就花了些時間將其看完,並且用這篇文章當作筆記

Introduction

  • 當前的 TCP connection 中,大部分的封包都是小size的,如何快速的處理這些封包是個提升效能的重點
  • 根據這篇論文,在特定的網路環境下(large cellular network),超過 90% 的 TCP 封包都小於 32KB,超過 50% 的則是小於 4KB。
  • 當前的 Linux Kenrl 的架構使得處理小封包的速度沒有很好的表現。
  • 目前世界上有很多種方案嘗試解決此問題。
    • 修改 kernel 的,如 MegaPipe, FlexSC
      • 在 user-space 提供高速的 Packet I/O,這部分通常是直接跟網卡操作,跳過 kernel。如 netmap, DPDK, PSIO。
  • 上述的方案都難以應用到現有的系統
    • 改 kernel code 對於已經應用的伺服器來說,不是那麼方便
      • user-space library 的缺點
      1. 沒有實作 TCP stack,所以使用者都要自己想辦法去處理整個data (每個 Layer 自行處理)
      2. 沒有提供統一的介面,現存的應用程式很難 porting
  • 本篇 paper 提出的一個新的架構 mTCP,宗旨就是解決上述所有問題
    • 不修改 kernel, 實作於 user-space
      • 讓現有的應用程式可以容易使用,快速轉換
      1. 提供良好的 wrapper 給當前的 BSD-socket API,同時也提供 event 相關的(epoll)
      2. 實作 TCP stack
    1. 架構上要解決當前 kernel 的架構問提,提升整體的處理速度
Read more »

Introduction

此篇文章用來說明在當前 kernel 中, switchdev 相關的檔案有哪些,哪些是 switchdev 的核心,哪些是與原先的 linux kernel 整合,同時簡述一下各整合的用途為何。

Read more »

Introduction

  • Switchdev 在 linux kernel 3.19+ 以後才正式支援的,此專案希望能夠讓整合 hardware switches 與 Linux kernel。
  • 以前的 hardware switch 都有實作自己的 L2/L3 offloading,同時廠商會在 user space 提供自己的 tool 用來操控該 switchdev。
  • 在此架構下,很多常用的 user space tool,如 ethtool, ip, brctl ..等都沒有辦法針對 hardware swtich 去控制,這會使得上層的軟體都要針對不同的底層硬體去客製化處理
  • 為了解決這個問題,希望在 kernel 中加入一層 switchdev,各廠商在 kernel 內實現自己 driver 的 switchdev,然後 swtichdev 本身會與原本的 user space tool 整合,這樣的話 user space 就不用額外提供 tool 了。

    Read more »

Introduction

此篇文章用來記錄最近遇到的一個問題,在一個執行 NFQUEUE 的系統上,當一個尚未被 conntrack 紀錄的連續 UDP 封包經過系統且都經過 NFQUEUE 處理後,第二個 UDP 封包都會遺失的問題。

NFQUEUE

  • 一種 Queue,由 netfilter (ipables) 所提供的一種 target,能夠將封包內容藉由 netlink/nmap 送到 user-space 去,大部分的 IPS/IDS 都會藉由此方式來分析封包,如 suricata。
  • User space 有對應的 library 可以用來接收此封包,參考此link
  • 相關的 tutorial 可參考

    Read more »

這篇文章要跟大家分享在 OpenvSwitch 裡面內建的 Bonding 模式,相對於傳統 Linux Kernel 自帶的六種模式,OpenvSwitch 只有提供三種模式。這三種模式的用途以及分配的方式都完全不同,完全取決於使用者本身的環境需求,來判斷自行的環境需要採用哪種模式,有單純的 Active-backup 模式,也有 Active-Active 的模式。再 Active-Active 的模式中要如何去分配封包,可以針對 Layer2 也可以針對 Layer3/4 的環境來使用,這部份就是依賴管理員去思考的。

Read more »