【ios 内核】源码解读（4） 锁的内核实现
得益于GCD提供的队列和分发机制，我们将很多原本需要新建线程，用各种锁来同步的事情甩给了GCD来完成，达到了业务层面 Lock-Free 编程的目的（GCD本身是用了一些信号量等锁操作的）。我们也可以选择自己建NSThread来管理线程和线程同步，本文主要介绍底层有哪些同步机制，以及它们具体是怎么实现的。
Mach下最底层的锁
在osfmk/arm/locks.h里，定义了三种底层的锁：spin lock, mutex和rw_lock。对这三个种锁宽泛的定义已经是老生常谈的内容了，这里先主要介绍一下它们在mach中的具体结构，后续再以mutex为例详解具体实现。
Spin Lock 自旋锁
自旋锁是一个忙等待的锁，简单来讲就是如果其他线程已加锁，自身线程用一个死循环来判断对方是否已解锁。由于线程会处于忙等待状态，所以自旋锁不适合被锁住过长时间。自旋锁在osfmk/arm/locks.h中的定义如下：
typedef struct {
struct hslock hwlock;
uintptr_t type;
} lck_spin_t;
其中type指明了锁的类型，如LCK_SPIN_TYPE等。而hslock是最底层的锁，定义在osfmk/arm/hw_lock_types.h中：
struct hslock {
uintptr_t lock_data;
};
typedef struct hslock hw_lock_data_t, *hw_lock_t;
其中lock_data可以用来存储额外的数据，一般用于存储锁的状态。hslock提供了最基础的lock，unlock，try，held等操作，被具体应用在自旋锁的加锁解锁等操作中，后面会具体介绍一部分。
Mutex 互斥锁
互斥锁是比较常用的锁，如果一个线程在请求互斥锁时，其他线程已经加锁，那么该线程就会进入睡眠状态，直到后续线程解锁将其唤醒，这里要注意的是同一个线程如果请求两次互斥锁的话，会触发一个内核异常。结构体定义如下：
typedef struct _lck_mtx_ {
union {
uintptr_t lck_mtx_data; /* Thread pointer plus lock bits */
uintptr_t lck_mtx_tag; /* Tag for type */
};
union {
struct {
uint16_t lck_mtx_waiters;/* Number of waiters */
uint8_t lck_mtx_pri; /* Priority to inherit */
uint8_t lck_mtx_type; /* Type */
};
struct {
struct _lck_mtx_ext_ *lck_mtx_ptr; /* Indirect pointer */
};
};
} lck_mtx_t;
可以看到它主要由两部分组成，第一部分是data或者tag，用于存储状态或者类型等数据。第二部分是用于存储与该互斥锁相关的等待着信息，包括等待着的数量，优先级，类型等，用于unlock时唤醒判断。但是这里只存储了数量等参数信息，真正的锁序列是直接以run queue的形式存储在thread结构体中的。这里有两个与解锁相关比较关键的宏定义：
#define LCK_MTX_EVENT(lck) ((event_t)(((unsigned int*)(lck))+((sizeof(lck_mtx_t)-1)/sizeof(unsigned int))))
#define LCK_EVENT_TO_MUTEX(event) ((lck_mtx_t *)(uintptr_t)(((unsigned int *)(event)) - ((sizeof(lck_mtx_t)-1)/sizeof(unsigned int))))
在mutex解锁的过程中，是通过发送mutex消息来完成唤醒其他线程的，这里有一个mutex与event相互转化的过程，可以看到lck_mtx_t这个结构体是以unsinged int对齐的，这里用lck_mtx_t的大小-1除以unsinged int的大小，就是指向了这个结构体的最后一个padding，而第二个union两个struct都正好只占一个padding，也就正好指向了第二个uinon部分。也就是说这是一个指向跟结构体和第二个结构体之间的指针转移操作，也是内核代码中常见骚操作之一。（满脑子都是骚操作.jpg）
R_W Lock 读写锁
读写锁是用来保证同时读，单独改的锁，也就是允许多个线程同时执行读操作，但是写操作同时只有一个线程可以执行，并且要在所有已发生的读写操作完成之后才能进行，相对应的这里读写锁提供了两个加锁方法：shaed和exclusive。
读写锁的概念与GCD中队列任务屏障以及接下来讲的内存屏障十分相似，但是GCD是面向队列的，CPU内存屏障是面向过程的。读写锁的结构体中主要定义了一些状态，flag字段等，具体可以在locks.h中查看。
锁的具体实现
接下来就以mutex(互斥锁)为例详细介绍下锁的实现，不过在看具体源码之前，需要了解一些基础的原子操作知识，首先看一下在locks_arm中几个关键的定义：
#define memory_barrier() __c11_atomic_thread_fence(memory_order_acq_rel_smp)
#define load_memory_barrier() __c11_atomic_thread_fence(memory_order_acquire_smp)
#define store_memory_barrier() __c11_atomic_thread_fence(memory_order_release_smp)
// Enforce program order of loads and stores.
#define ordered_load(target, type) \
__c11_atomic_load((_Atomic type *)(target), memory_order_relaxed)
#define ordered_store(target, type, value) \
__c11_atomic_store((_Atomic type *)(target), value, memory_order_relaxed)
这里分别定义了读写内存壁垒，顺序读写等一些过程，是所有锁的基础，用到了atomic_thread_fence，atomic_load，atomic_store等操作。这里不可避免得要先从编译阶段到应用层来介绍Memory Order：
编译阶段的指令重排
我们写这样一段简单的代码，用普通编译和开启编译优化的命令分别编译：
可以看到B的赋值操作在两段汇编代码中的位置是不一样的，因为开启编译优化后，编译器为了达到节约寄存器的使用，减少操作指令之类的目的，会根据情况调整指令，或者进行指令重排之类的操作。如果在代码中因为自身业务原因希望避免这样的指令重排，我们在locks_arm.c中有如下一个定义：
// Prevent the compiler from reordering memory operations around this
#define compiler_memory_fence() __asm__ volatile ("" ::: "memory")
这是GCC提供的其中一种编译阶段内存壁垒（同时包含读写的壁垒），可以保证该行前后的读和写操作不会越过这个壁垒，保证前后两个部分的相对有序（每个部分内还是可以重排）。
C++中的内存顺序和原子操作
C++中提供了一系列原子操作的接口，其中最常用的是atomic_load和atomic_store
template< class T >
T atomic_load_explicit( const std::atomic<T>* obj,
std::memory_order order ) noexcept;
void atomic_store_explicit( std::atomic<T>* obj,
typename std::atomic<T>::value_type desr,
std::memory_order order) noexcept;
顾名思义，这是对一个操作对象的原子存和原子读操作，除了指定操作对象和目标对象之外，这里还提供了一个具体的std::memory_order参数，代表可以指定的具体内存顺序规则，在锁相关的代码中主要用到了以下两种：
（1）Acquire/Release
这是一个对应多线程下保证某一个变量读写有序的规则。即acquire用于读（#LoadStore和#LoadLoad，保证后序读写操作都在这个load操作后进行），Release用于写（#LoadStore和#StoreStore，保证前序读写操作都在这个store操作前进行）。关于这个，这篇文章讲述得非常清楚了，引用一张图：
（2）memory_order_relaxed
松弛的内存顺序，只保证在一个线程内，读写操作不能被重新排序，但是多个线程的无法保证。
完整的定义可以看：https://gcc.gnu.org/wiki/Atomic/GCCMM/AtomicSync 。这里就不重复阐述了，里面讲的十分细致和完整。
Mutex的加锁和解锁过程
这里我们以mutex为例详细看下加锁和解锁过程。首先，这里加锁需要简单分为两个部分：对lck变量本身的锁（防止同时访问lck）以及mutex锁本身。
（1）对lck变量的锁：interlock
interlock是啥呢，话不多说，直接看interlock的宏定义：
#define interlock_lock(lock) hw_lock_bit ((hw_lock_bit_t*)(&(lock)->lck_mtx_data), LCK_ILOCK_BIT)
interlock其实就是把lock的lck_mtx_data调用hw_lock_bit设置成LCK_ILOCK_BIT（这个变量是0）。hw_lock_bit从功能上来讲，很好理解，它是一个把一个变量用类似spinlock的方式设置成对应的值，但是必须是自己设的。（举个例子，目标把变量a设置成1，如果设置的时候发现a已经是1了，说明有其他操作把它持有了，一直等到a!=1或者超时的时候，再设置a=1）。具体流程如下：
通过hw_lock_bit，可以防止两个线程同时对lock进行操作，防止加锁过程被打断等。要注意这里只是保证lock变量在加解锁过程中不被打断。
（2）Mutex锁
Mutex的核心加锁过程主要在lck_mtx_lock_contended中：
for ( ; ; ) {
if (atomic_compare_exchange(&lock->lck_mtx_data, 0, LCK_MTX_THREAD_TO_STATE(thread),memory_order_acquire_smp, FALSE))
return;
interlock_lock(lock);
interlock_held:
state = ordered_load_mtx(lock);
holding_thread = LCK_MTX_STATE_TO_THREAD(state);
if (holding_thread == NULL)
break;
ordered_store_mtx(lock, (state | LCK_ILOCK | ARM_LCK_WAITERS)); // Set waiters bit and wait
lck_mtx_lock_wait(lock, holding_thread);
}
主要过程如下：
- 放一个死循环，首先在这个死循环中首先用interlock将lock变量加锁。
- 从lock的
lck_mtx_data中取出state。 - 将state转换为thread，检测当前是否有线程持有了这个锁。
- 如果持有了锁，直接break，进行接下来的加锁操作（接下来就是设置lock的state之类的）
- 如果有线程已经持有，那么执行wait操作，等待唤醒。（这一步后面详细介绍）
这里有两个重要的概念，state和thread，他们是可以相互转换的：
/*
* Lock state to thread pointer
* Clear the bottom bits
*/
#define LCK_MTX_STATE_TO_THREAD(s) (thread_t)(s & ~(LCK_ILOCK | ARM_LCK_WAITERS))
/*
* Thread pointer to lock state
* arm thread pointers are aligned such that the bottom two bits are clear
*/
#define LCK_MTX_THREAD_TO_STATE(t) ((uintptr_t)t)
thread_t是一个unsinged int，由于线程创建时的指针是内存对齐的，所以最后两个bit可以被用于存储当前的状态，state转换为thread指针只要将最后两位置0就是指针的地址。
lck_mtx_lock_wait是加锁过程中最重要的一步，函数中首先是设置holding线程的调度优先级，然后修改了基本属性（如mutex中waiter是变量加1等），最终调用了thread_block函数将线程挂起。而与lck_mtv_lock_wait相对应的，是在解锁过程中调用的lck_mtx_unlock_wakeup函数：
/*
* Invoked on unlock when there is contention.
* Called with the interlock locked.
*/
void
lck_mtx_unlock_wakeup (lck_mtx_t *lck, thread_t holder)
{
thread_t thread = current_thread();
lck_mtx_t *mutex;
//xxxxx….
assert(mutex->lck_mtx_waiters > 0);
if (mutex->lck_mtx_waiters > 1)
thread_wakeup_one_with_pri(LCK_MTX_EVENT(lck), lck->lck_mtx_pri);
else
thread_wakeup_one(LCK_MTX_EVENT(lck));
if (thread->promotions > 0) {
spl_t s = splsched();
thread_lock(thread);
if (--thread->promotions == 0 && (thread->sched_flags & TH_SFLAG_PROMOTED))
lck_mtx_clear_promoted(thread, trace_lck);
thread_unlock(thread);
splx(s);
}
//xxxx….
}
可以看到当mutex->lck_mtx_waiters数量大于1或者等于1时，分别调用了thread_wakeup_one_with_pri和thread_wakeup_one来从运行队列中根据优先级等来唤醒对应的线程。可以看到这里用到了前面介绍的LCK_MTX_EVENT来将lck转换为mutex消息。这里最终会走到waitq_wakeup64_one_locked中调用thread_go来唤醒下一个待解锁的线程。
总结
原子操作是所有锁和同步的基础，编译阶段GCC提供了编译过程中的内存壁垒，而多线程环境下应对不同的需求可以使用不同程度的内存顺序模型（例如完全顺序一致或者基于acquire和release的等）。
本文简单介绍了locks_arm.c下的三个锁：自旋锁，互斥量和读写锁。自旋锁可以说是无处不在的锁，因为如果要实现例如加锁一个lock变量这种马上就解锁的操作，自旋锁无疑是开销最小的，因此无论是互斥量还是读写锁的实现过程中，都依赖了自旋锁来进行小范围的同步。互斥量的实现依赖了线程调度模块，这里只做了简单介绍，后续有机会详细介绍下。除这三个最底层的锁之外，上面还封装和实现了信号量，递归锁等我们常见的同步模型，以及针对I/O操作的一些锁等等，大部分都是以这里介绍的三种锁为基础搭建的。
最后关于CPU相关的内存知识，强烈推荐一篇能看一年的论文，What Every Programmer Should Know About Memory：https://www.akkadia.org/drepper/cpumemory.pdf （头有点大.jpg）
参考文献：
【1】Darwin-XNU源码：https://github.com/apple/darwin-xnu
【2】GCC Memory Order: https://gcc.gnu.org/wiki/Atomic/GCCMM/AtomicSync
【3】OS X Internals: http://venom630.free.fr/pdf/OSXInternals.pdf
【4】Acquire and Release Semantics: http://preshing.com/20120913/acquire-and-release-semantics/
【ios 内核】源码解读（3） 详解ios是怎么malloc的（上）
iOS和Mac OS从顶到下有一系列长长的不同alloc函数，NSObject的alloc和allocWithZone(这里oc层的NSZone已经不使用了)，Core Foundation里的CFAllocatorAllocate，libc里的malloc，内核的vm_allocate和kalloc等。今天我们从libc开始，看一下从用户态到内核态的malloc/allocate是怎么工作的。
用户态的Malloc Zone
Memory Zone是一个我们在很多操作系统里面都能见到的一个概念，例如在Linux中有ZONE_DMA，ZONE_NORMAL，ZONE_HIGHMEM等memory cache，windows中有memory pool，而在Darwin的libmalloc中，以szone_t的形式存在。那么memory zone存在的意义是什么呢？
在上一篇讨论虚拟内存中，我们提到进程是建立在虚拟内存的基础之上的，虚拟内存与物理内存通过pmap来建立映射。如果每次进行内存分配，都需要从顶到下走一遍插入虚拟内存页(vm_page)，然后通过pmap和不同架构的内存地址映射表来建立映射，会是一件缓慢而痛苦的事情。而memory zone也被称为memory cache，就是一段预先分配好的内存空间，顶层在需要分配内存的时候，直接去zone里面取，按需不足时再构建新的内存映射，达到高效分配等目的。
要注意的是，用户态的libmalloc有szone_t，而内核mach层有mach zone，这两个是完全不同的东西。下面我们详细介绍用户态和内核态的zone，它们之间的联系和具体的作用。
libmalloc中的malloc和szone_t
在libmalloc中，memory zone是在magazine_zone.h中定义的szone_t，该库中的大多数操作都是以这个结构体为基础的。而malloc操作从源码来看，最终是由magazine_malloc.c中的szone_malloc_should_clear函数完成的。首先我们来看几个定义：
#define SHIFT_TINY_QUANTUM 4
#define TINY_QUANTUM (1 << SHIFT_TINY_QUANTUM)
#if MALLOC_TARGET_64BIT
#define NUM_TINY_SLOTS 64 // number of slots for free-lists
#else // MALLOC_TARGET_64BIT
#define NUM_TINY_SLOTS 32 // number of slots for free-lists
#endif // MALLOC_TARGET_64BIT
/*
* The threshold above which we start allocating from the small
* magazines. Computed from the largest allocation we can make
* in the tiny region (currently 1008 bytes on 64-bit, and
* 496 bytes on 32-bit).
*/
#define SMALL_THRESHOLD ((NUM_TINY_SLOTS - 1) * TINY_QUANTUM)
/*
* The threshold above which we start allocating from the large
* "region" (ie. direct vm_allocates). The LARGEMEM size is used
* on systems that have more than 1GB RAM.
*/
#define LARGE_THRESHOLD (15 * 1024)
#define LARGE_THRESHOLD_LARGEMEM (127 * 1024)
对于不同大小的内存，分配方式是不一样的。这里通过SMALL_THRESHOLD和LARGE_THRESHOLD两个阈值将内存分配分成了tiny，small和large三种模式
Tiny内存分配
对小于等于SMALL_THRESHOLD（64位系统下1008字节，32位系统下496）的内存分配，系统会走tiny的内存分配方式。根据之前讲的，memory zone是一块预先分配好的内存，作为szone_t的一部分，在tiny内存分配中，自然是用到若干块预先分配好的内存。
这里用到了一个核心概念“quantum”，一个quantum是内存分配中的最小单位，大小为16个字节，也就是说任何以tiny形式分配的内存都是16字节的倍数。一块预先分配好的内存被均分成了一个个连续的quantum和一个标记使用信息的bitmap，如下图所示：
那么我们如何能够确定该块区域中哪些部分是可用的，哪些部分是不可用的呢？主要依赖一个bitmap和如下几条规则：
- 一个完整的bitmap由两个子bitmap（header bitmap和in use bitmap）组成。每个子bitmap的大小为 (一个预先分配好的内存中quantum数量) * 1bit，中间用0xFFFFFFFF分隔。
- 如果一块区域已经被使用，那么这块区域的第一个quantum在header bitmap 和 in use bitmap中对应的值都是1.
- 如果一块区域是空闲的，那么这块区域的第一个quantumheader bitmap 和 in use bitmap中对应的值分别是1和0.
- 其他情况下，quantum在 header bitmap中的值是0.
- 其他情况下，quantum在in use bitmap中对应的值无关紧要，无需额外操作，爱是几就是几。
其实一句话就能总结，header bitmap是用来标记一个块的起始位置的，为1的就是一个块的起始。那么如何区分是已分配还是空闲呢？in use bitmap中为1的就是一个已分配块的起始，如果header bitmap为1，in use bitmap为0就是空闲块的起始。
那么我们以上图为例，阐述下空闲区1是怎么被定位的：
- 从左往右扫描，发现q0在两个bitmap中的值都是1，那么表明q0是一块已使用区域的开始。
- 继续扫描，发现q2到qi-i在header bitmap中的值都是0，说明这是已使用区域的一部分。
- 扫描到qi，发现qi在header bitmap中是1，in use bitmap中是0，说明这是空闲块的起始
- 继续扫。。。。
在此基础之上，连续的quantums组成的空闲块被存储在了一系列链表上，如下图所示：
tiny_free_list是一个双向链表，一共有64个元素，每个双向链表中都存储着另一个双向链表。第K个链表中存储的就是所有“连续K个quantum组成的区域”。每次我们需要分配内存的时候，就根据需要分配内存的大小除以每个quantum的大小得到应该需要几个连续的块，找到合适的就分配，整个内存不够分配时就开辟新的region。这里具体的分配算法可以在magazine_tiny.c的tiny_malloc_from_free_list函数中查看。
small内存分配
对于大于SMALL_THRESHOLD，小于等于LARGE_THRESHOLD的内存，就走small内存分配。small内存分配和tiny十分相似，只是每个quantum的大小变了，如下：
#define SHIFT_SMALL_QUANTUM (SHIFT_TINY_QUANTUM + 5) // 9
#define SMALL_QUANTUM (1 << SHIFT_SMALL_QUANTUM) // 512 bytes
另外header bitmap也用了不同的定义，如下：
如图所示，每个quantum都映射到了一个16bit的区域上，这16bit被拆分成了两个部分：
- 第1bit代表使用情况，0代表空闲，1代表已分配。
- 后15bit组成的数字代表连续的quantum个数。
| 只有连续区域的第一个quantum被标记，如 0 | k 就代表从该quantum开始，后面连续K个快都是空闲的，非常直观。 |
large内存分配
对于大于LARGE_THRESHOLD的内存，走large内存分配。一块large内存是用一个large_entry_t来描述的：
typedef struct large_entry_s {
vm_address_t address;
vm_size_t size;
boolean_t did_madvise_reusable;
} large_entry_t;
这里就直接操作虚拟内存层的内存分配了，内存分配操作由vm_allocate函数完成，注意这里的address是高地址位的地址，address+size是低地址，由于是通过XNU的vm_allocate来直接分配，这里的其实和终结地址一定是页对齐的。所有的大内存会被根据地址哈希在一个数组里：
large_entry_t *large_entries; // hashed by location; null entries don't count
大内存的整体处理定义在magazine_large.c里，里面还有一些cache相关的操作等，这里就不展开了。
总结
对于不同大小的内存分配，libmalloc采用了tiny，small，large三种分配方式，主要目的是为了
- 更加高效的内存分配。
- 更合理的内存利用率。
由于日常内存分配大部分都会落在tiny和small中，通过预分配内存块，构建free_list等操作，一次内存分配大概率可以通过几次链表操作和几个bit位操作就能完成，避免了每次都构建虚拟内存，映射到物理内存的尴尬场面，在保证高效的前提下，通过quantum分区来尽量保证内存利用率。
本文还只介绍了用户态的malloc，XNU内部虚拟内存的分配，它与用户态之间的联系，用户态memory zone和内核态memory zone之间的关系等，下次继续详细介绍。
参考文献
【1】Darwin-XNU源码：https://github.com/apple/darwin-xnu
【2】Mac OS® X Internals： http://venom630.free.fr/pdf/OSXInternals.pdf
【3】libmalloc源码：https://opensource.apple.com/source/libmalloc/libmalloc-140.40.1/
【ios 内核】源码解读（2） 虚拟内存
内存管理一直是操作系统几大核心内容之一，线程调度，文件加载，事件处理等操作都是建立在内存管理的基础之上。现代操作系统为了达到适配各种硬件架构，方便上层操作等目的都会引入虚拟内存的概念，本文主要介绍虚拟内存在Darwin中是如何实现的。
Mach下虚拟内存结构
Mach提供了一套非常全面的底层虚拟内存机制，提供给诸如BSD层的_Malloc()，可执行文件加载等等模块使用。下面话不多说直接上图看一下整体结构并且分具体模块解释（为了方便理解只保留的结构相关的部分，省略了大部分属性变量，完整的类定义可以在vm_map.h等文件中查看）
vm_map
处于龙头老大低位，宏观上看就是代表了若干段地址空间的映射，它地址空间是由一个vm_map_entry的双向列表组成（按照地址排序）。其中的pmap属性是用于映射到具体的物理地址的，会依据硬件的变化而变化。在上一篇讨论mach-o文件加载的过程中，load_machfile有如下代码：
pmap = pmap_create(get_task_ledger(ledger_task),
(vm_map_size_t) 0,
result->is64bit);
map = vm_map_create(pmap,
0,
vm_compute_max_offset(result->is64bit),
TRUE);
这里先创建了一个pmap然后根据pmap创建了vm_map，该vm_map对象后续被用于加载各个段，启动进程等，代表了整个进程的地址空间，并且虚拟地址的最大offset设为了64位/32位系统下最大的寻址空间。
vm_map_entry
vm_map所持有的链路中的一个节点，entry顾名思义代表一段内存的入口，并且这里的内存是一段连续的虚拟内存。内存的权限控制信息（protection信息，例如r/w/x等对内存页的操作）也存储在该部分。一个vm_map_entry持有一个vm_map_object的union，它通常指向一个vm_object的双向链表，也可以是一个子的vm_map。在mach-o文件加载过程中的map_segment函数中，有如下代码：
ret = vm_map_enter_mem_object(
map,
&cur_start,
cur_end - cur_start,
(mach_vm_offset_t)0,
VM_FLAGS_FIXED,
cur_vmk_flags,
VM_KERN_MEMORY_NONE,
IPC_PORT_NULL,
0, /* offset */
TRUE, /* copy */
initprot, maxprot,
VM_INHERIT_DEFAULT);
这里load_segment的过程就是将mach-o文件中的段映射到虚拟内存中去，这里将每一段分成了一个vm_map_entry，由于vm_map_entry内的地址是连续的，通过随机偏移量加上段本身大小等信息，达到了既保证段内相对位置不变，又可以把各个段随机映射到不同位置的目的。
vm_object
代表vm_map_entry指向具体的内存，他主要是由一个vm_page的双向链表(memq)，一个负责内存swap等操作的pager（下面详细介绍）和一些其他的属性标识等组成。
pager
由于实际的物理内存数量是有限的，如果所需内存超过RAM中可用内存的数量，就需要将内存暂存到列如磁盘，文件，设备等处，用到时再拿回来，达到用户态无感知循环使用内存的目的，这就是内存swap操作。每个操作系统基本都会有一套自己的swap机制，Mach的内存swap是由pager实现的。
首先pager是一个memory_object对象，定义如下：
/*
* "memory_object" and "memory_object_control" types used to be Mach ports
* in user space and can be passed as such to some kernel APIs.
* Their first field must match the "io_bits" field of a
* "struct ipc_object" to identify them as a "IKOT_MEMORY_OBJECT" and
* "IKOT_MEM_OBJ_CONTROL" respectively.
*/
typedef struct memory_object {
mo_ipc_object_bits_t mo_ikot; /* DO NOT CHANGE */
const struct memory_object_pager_ops *mo_pager_ops;
struct memory_object_control *mo_control;
} *memory_object_t;
它是一个可以被用于在用户空间与硬件端口通信的标准。在Mach中，常见的分页器有Default Pager(默认分页器)，VNode Pager(用与内存与文件的映射)，Device Pager（设备）等。所有的分页器都实现了一系列标准接口，其中最重要的就是page_in和page_out。
/*
* Request data from this memory object. At least
* the specified data should be returned with at
* least the specified access permitted.
*
* [Response should be upl commit over the specified range.]
*/
routine memory_object_data_request(
memory_object : memory_object_t;
offset : memory_object_offset_t;
length : memory_object_cluster_size_t;
desired_access : vm_prot_t;
fault_info : memory_object_fault_info_t);
处理page_in请求，也就是从后备存储读页进来，读到从memory_object的offset为起始，offset_length为终点的区域。
/*
* Return data to manager. This call is used in place of data_write
* for objects initialized by object_ready instead of set_attributes.
* This call indicates whether the returned data is dirty and whether
* the kernel kept a copy. Precious data remains precious if the
* kernel keeps a copy. The indication that the kernel kept a copy
* is only a hint if the data is not precious; the cleaned copy may
* be discarded without further notifying the manager.
*
* [response should be a upl_commit over the range specified]
*/
routine memory_object_data_return(
memory_object : memory_object_t;
offset : memory_object_offset_t;
size : memory_object_cluster_size_t;
out resid_offset : memory_object_offset_t;
out io_error : int;
dirty : boolean_t;
kernel_copy : boolean_t;
upl_flags : int);
处理page_out请求，也就是把页存到后备存储中去，也是从memory_object的offset为起始，offset_length为终点的区域，将数据拷贝到后备存储中，并且将其标记为可用。
在mach-o文件加载过程中，就是将文件内容作为一个vnode，然后利用page_in映射能力把文件中的不同段，签名等内容加载到内存中去。
vm_page
真正映射到物理页的部分，一个页可以有多种状态：驻留，交换到后备存储，被加密，clean，dirty等。这里要注意的是，这里一个vm_page_t的大小是64个字节，这是因为在arm64和x86_64架构下，一个cache line的大小正好是64字节，在内存对齐的前提下，方便CPU一次性读取一个页。（关于CPU cache line的简单介绍 https://stackoverflow.com/questions/3928995/how-do-cache-lines-work，CPU各级缓存策略详细介绍和示例：http://igoro.com/archive/gallery-of-processor-cache-effects/）
pmap
pmap是vm_map持有的真正将虚拟内存映射到物理内存的模块，从逻辑设计的角度上来讲，它可以分为两个部分：硬件无关层和硬件相关层。
硬件无关层
从实际实现上来讲，所谓的硬件无关层其实并没有做什么事情，但是这部分定义了与上层交互的硬件无关的标准API（详细可以在<vm/pmap.h>中找到）。这里定义了诸如pmap_create，pmap_enter等创建和管理内存映射的API，上层可以不需要关心具体的硬件实现，依照标准来处理内存。
硬件相关层
这里是具体实现虚拟地址映射的地方，在苹果的Darwin源码中，具体实现了arm，i386，x86_64等硬件架构的pmap。每个硬件架构都有一套自己的虚拟地址到物理地址的映射方式，但是都无外乎通过页表，PTE（page table entry）等完成地址映射。下面以arm为例，简单描述下虚拟地址到物理地址的映射过程。
首先，虚拟地址中内核空间（kernal space，只被操作系统内核使用）和用户空间（比如运行app用到的内存）是完全分离的，如下图所示：
这里内核空间和用户空间的基地址是在Translation Table Base Registers (TTBR0_EL1) 和(TTBR1_EL1)中指定的，比如说图例中用户空间可以访问0x0 到 0x0000FFFF_FFFFFFFF，内核空间可以访问0xFFFF0000_00000000 到 0xFFFFFFFF_FFFFFFFF 的虚拟地址空间，也就是前16位必须是0或者1，否则就会触发一个地址错误。
在此基础之上，假设我们要映射一个42bit的虚拟地址空间到48bit的物理地址页（其实armV6支持的是64KB和4KB两种大小的页），流程如下：
这里整体流程如下：
- 首先看虚拟地址的第63到42位，当它们全等于0的时候，说明需要使用TTBR0为基地址的虚拟地址转换表。
- 根据第41到29位的数值作为表内偏移量，找到表内对应的具体PTE（page table entry），然后从改项中读出物理页的基地址。
- 将从PTE中读出的基地址与剩下的第28到0位拼接，成为真正的具体物理地址。
这里只是最简单的一个转换表的情况，通常会有多个转换表，也就是前一个读出的PTE作为下一张表的基地址，然后加上虚拟地址的最后一段继续拆分的偏移量来定位新的PTE的做法，达到段页分离等目的。
参考文献
【1】Darwin-XNU源码：https://github.com/apple/darwin-xnu
【2】Mac OS® X and iOS Internals： http://newosxbook.com/MOXiI.pdf
【3】arm手册：https://www.scss.tcd.ie/~waldroj/3d1/arm_arm.pdf
【ios 内核】源码解读（1） darwin架构和可执行文件加载
作为最古老的现代操作系统之一，Mac OS一直是被人们相对讨论得最少的(相比于Linux和Windows)。这里打算开一个系列来具体讲讲Mac OS和iOS(用乔老爷发布会的话说:”We run OS X on iPhone”)内核的一些知识点，内容主要以源码为主，结合官方文档详细介绍操作系统底层的一些内容。这个系列预计会包含可执行文件加载，虚拟内存，线程，boot等。本篇主要介绍一些宏观上架构作为引言，并详细介绍可执行文件的加载过程（特别注意的是Mach-O文件结构和一些运行时的知识实用性和对理解操作系统的帮助作用都很大，但是已经有数不尽优秀的资料可以参考，这部分并不是本篇的重点）。
简单看一下Darwin的架构
iOS和 Mac OS 都是Unix标准的操作系统. 所谓Unix标准，就是按照POSIX (Portable Operating System Interface)标准家族来构建的操作系统，该标准定义了一整套内存，线程，文件，I/O处理等功能的标准接口。iOS的基础系统架构如下：
Application Frameworks 和 Core Frameworks是我们这些拖控件工程师接触得最多的部分，苹果在这里提供了一整套十分友好的API来搭建APP。而Darwin处于最底层，提供了最基础的例如线程模型，调度，内存映射和管理等一系列功能，它是Unix操作系统的一个具体实现，稍微详细的结构如下：
苹果官方把Darwin分成了五个主要的模块：
Mach，主要提供了：
- 虚拟内存
- 进程和线程的底层描述
- 任务调度
- 跨进程通信（IPC）
提供了最底层的处理，管理一些列如CPU，内存等系统资源，为其他模块提供了一个基于消息中心的处理模块。
BSD，主要提供了：
- 文件系统
- 网络
- UNIX安全模型
- BSD进程模型（包括进程ID，信号和相关API等）
- 大部分POSIX标准的API
- pthread以及相关的同步策略
BSD层是建立在Mach之上的，以Mach提供的功能模块为基础搭建的实现了POSIX标准API的一个组件。相比与Mach层，BSD提供了更高层的功能描述，贴合unix的系统设计。
Networking
File Systems
这两个模块顾名思义负责网络和文件系统，属于BSD负责的范畴，是它的子模块。
I/O Kit
负责硬件交互，属于Mach的子模块。
Unix常见可执行文件，fat以及Mach-O
Unix可执行文件的类型是由文件头部的一个uint32_t类型的”magic”字段定义的，Windows下有PE32/PE32+，Linux下有ELF格式的可执行文件，Mach下主要有Universal binaries(fat)和Mach-O两种。
Universal Binaries(fat)
顾名思义，通用的二进制文件，就是在各个不同架构下都可以适配或运行的文件。如何做到通用的就是把不同硬件架构下的文件整合到了一个文件中，我们直接看一下<mach-o/fat.h>里面的定义：
#define FAT_MAGIC 0xcafebabe
#define FAT_CIGAM 0xbebafeca /* NXSwapLong(FAT_MAGIC) */
struct fat_header {
uint32_t magic; /* FAT_MAGIC */
uint32_t nfat_arch; /* number of structs that follow */
};
struct fat_arch {
cpu_type_t cputype; /* cpu specifier (int) */
cpu_subtype_t cpusubtype; /* machine specifier (int) */
uint32_t offset; /* file offset to this object file */
uint32_t size; /* size of this object file */
uint32_t align; /* alignment as a power of 2 */
};
它主要由一个header和若干个fat_arch组成的，header中标明了文件类型(magic)和fat_arch的个数。每个fat_arch标明了对应的cpu类型，在文件内的偏移量和大小等。例如用lipo命令看ffmpeg的libavcodec.a文件，可以看到是四个cpu架构下文件的集合：
Mach-O文件
关于Mach-O文件，可以说是老生常谈的一个话题了，关于分析Mach-O头部，各个段和节的组成以及含义，网上有很多优秀的文章分析，就不在这里重复描述了，完整的定义可以看 https://github.com/aidansteele/osx-abi-macho-file-format-reference（Mach-O Format Reference），以及苹果的官方文档：http://math-atlas.sourceforge.net/devel/assembly/MachORuntime.pdf（Mach-O Runtime Architecture）。后续在介绍虚拟内存，进程等内容的时候会结合Mach-O来分析。
Mach-O加载过程以及地址空间布局随机化（Address Space Layout Randomization）
地址空间布局随机化是通过随机化每次进程启动后各个段，节，堆栈等起始位置，来防止攻击者轻易修改程序的内容（例如修改内存中一个函数指针位置，如果每次加载，进程内各个部分的相对偏移量都是不变的话，就很容易做出通用的hook程序）。
下面我们直接从源码来分析Mach-O文件在load过程中是如何实现地址空间布局的随机化的：
1. load_machfile初始化vm_map和随机偏移量
Mach-O文件的加载会经过初始化镜像，加载镜像到内存，头部检测等过程，然后走到load_machfile开始真正解析文件内容。为了便于理解摘录了部分代码（完整代码可以在mach_loader.c中找到，这里只保留了一小部分并且加上了一些注释，请放心食用）
部分代码：
load_return_t
load_machfile(
struct image_params *imgp,
struct mach_header *header,
thread_t thread,
vm_map_t *mapp,
load_result_t *result
)
{
//xxx….
pmap_t pmap = 0; /* protected by create_map *///用于映射物理地址
vm_map_t map;//虚拟地址
int64_t aslr_page_offset = 0;//随机页偏移量
int64_t dyld_aslr_page_offset = 0;//动态库的随机页偏移量
int64_t aslr_section_size = 0;
int64_t aslr_section_offset = 0;
//xxxx….
//先创建一个映射物理地址的pmap
pmap = pmap_create(get_task_ledger(ledger_task),
(vm_map_size_t) 0,
result->is64bit);
//基于pmap创建一个虚拟地址入口
map = vm_map_create(pmap,
0,
vm_compute_max_offset(result->is64bit),
TRUE);
//xxxxx…
/*
* Compute a random offset for ASLR, and an independent random offset for dyld.
*/
//这里是具体计算随机偏移量的部分
if (!(imgp->ip_flags & IMGPF_DISABLE_ASLR)) {
//先计算整个section的大小和偏移量
vm_map_get_max_aslr_slide_section(map, &aslr_section_offset, &aslr_section_size);
aslr_section_offset = (random() % aslr_section_offset) * aslr_section_size;
//取一个随机数，模上最大可偏移页数，然后页对齐（就是乘以了页的大小）
aslr_page_offset = random();
aslr_page_offset %= vm_map_get_max_aslr_slide_pages(map);
aslr_page_offset <<= vm_map_page_shift(map);//页对齐，一个页的大小是2^page_shift
//这里计算方法和上面差不多
dyld_aslr_page_offset = random();
dyld_aslr_page_offset %= vm_map_get_max_loader_aslr_slide_pages(map);
dyld_aslr_page_offset <<= vm_map_page_shift(map);
//最后加上了整个section的偏移量
aslr_page_offset += aslr_section_offset;
}
//xxxxx…..
//调用parse_machfile来扫描文件和执行Load Command
lret = parse_machfile(vp, map, thread, header, file_offset, macho_size,
0, aslr_page_offset, dyld_aslr_page_offset, result,
NULL, imgp);
//xxxxxx…..
}
上面摘录了load_machfile部分函数代码（包含ASLR相关的部分）。
函数首先初始化了pmap，然后通过pmap创建了一个vm_map（vm_map是一段虚拟内存的入口，由一个vm_map_entry双向链表组成，最终映射到一系列vm_page。而映射到具体不同硬件的物理内存由pmap负责，后面会新开文章详细介绍Darwin的虚拟内存相关内容），该Mach-O文件内容会加载到这个vm_map中。
接着对于各个段的加载和动态库的加载分别计算了一个page_offset，具体的计算过程是先取一个随机数，然后跟最大的偏移页数取余，最后左移每个页的shift值进行页对齐（防止一个页里面有两个mach-o加载出来的东西等），最后加上整个section的offset，得到最终的偏移量。计算出来的偏移量会被用于parse_machfile。
2. parse_machfile执行Load Command
parse_machfile函数负责扫描各个段并执行相应的Load Command，先看看部分源码（也是只摘了一小部分，源码在mach_loader.c中）：
static
load_return_t
parse_machfile(
struct vnode *vp,//这里面存着文件信息
vm_map_t map,//之前传进来的虚拟地址入口
thread_t thread,
struct mach_header *header,
off_t file_offset,
off_t macho_size,
int depth,
int64_t aslr_offset,//随机偏移量
int64_t dyld_aslr_offset,//针对动态库的随机偏移量
load_result_t *result,
load_result_t *binresult,
struct image_params *imgp
)
{
//获取vnode的”memory object control”，里面有具体的”pager”来获取真正的页（虚拟内存相关知识，后续详细介绍）
/*
* Get the pager for the file.
*/
control = ubc_getobject(vp, UBC_FLAGS_NONE);
//xxxxx….
//PIE(Position-independent executable)，指代码的执行不依赖它的绝对地址
/*
* For PIE and dyld, slide everything by the ASLR offset.
*/
if ((header->flags & MH_PIE) || is_dyld) {
slide = aslr_offset;
}
//xxxxx…
/*
* Scan through the commands, processing each one as necessary.
* We parse in three passes through the headers:
* 0: determine if TEXT and DATA boundary can be page-aligned
* 1: thread state, uuid, code signature
* 2: segments
* 3: dyld, encryption, check entry point
*/
//四趟扫描，分别遍历Load Command
for (pass = 0; pass <= 3; pass++) {
//xxxxxx….
/*
* Loop through each of the load_commands indicated by the
* Mach-O header; if an absurd value is provided, we just
* run off the end of the reserved section by incrementing
* the offset too far, so we are implicitly fail-safe.
*/
offset = mach_header_sz;
ncmds = header->ncmds;
while (ncmds--) {
//xxxx..
/*
* Get a pointer to the command.
*/
lcp = (struct load_command *)(addr + offset);
oldoffset = offset;
//xxx….
/*
* Act on struct load_command's for which kernel
* intervention is required.
*/
switch(lcp->cmd) {
case LC_SEGMENT: {
//加载段
struct segment_command *scp = (struct segment_command *) lcp;
//xxxx…
ret = load_segment(lcp,
header->filetype,
control,
file_offset,
macho_size,
vp,
map,
slide,
result);
//xxxxx….
}
case LC_SEGMENT_64: {
//xxxx
}
case LC_UNIXTHREAD:
//开启一个unix线程，区别于LC_THREAD(加载一个mach线程，用于内核)
if (pass != 1)
break;
ret = load_unixthread(
(struct thread_command *) lcp,
thread,
slide,
result);
break;
case LC_MAIN:
//用于取代LC_UNIXTHREAD，主要用来加载主线程，设置entry point，栈大小等
//xxxx.
break;
case LC_LOAD_DYLINKER:
//加载动态库
if (pass != 3)
break;
if ((depth == 1) && (dlp == 0)) {
dlp = (struct dylinker_command *)lcp;
dlarchbits = (header->cputype & CPU_ARCH_MASK);
} else {
ret = LOAD_FAILURE;
}
break;
case LC_UUID:
if (pass == 1 && depth == 1) {
ret = load_uuid((struct uuid_command *) lcp,
(char *)addr + cmds_size,
result);
}
break;
//xxxxx…
}
//xxxx
}
}
}
可以看到这里总共分四趟扫描，每趟扫描去遍历head里所有的load command。第0趟检查TEXT段和DATA段是不是可以页对齐，第1趟加载线程（LC_UNIXTHREAD和LC_MAIN，加载主线程的entry point之类的），uuid以及代码签名相关命令，第2趟加载各个段(LC_SEGMENT)，最后一趟加载动态库，进行加密等。
这里随机偏移量作为了load_segment，load_unixthread等具体加载各个段，线程等函数的slide参数。下面以load_segment为例。
3.load_segment 和 map_segment
这两个函数主要负责将一个段的内容映射到虚拟内存中去，做了很多内存对齐的工作，首先看一下load_segment的结构(用otool命令可查看)：
这里标明了他在文件中的偏移量，大小，虚拟地址的位置和大小等信息。看load_segment的源码之前先看几个用于内存对齐的宏定义（每个都有我的注释，大家安心看）
//page_shift，每个page的大小为2^shift
#define VM_MAP_PAGE_SHIFT(map) ((map) ? (map)->hdr.page_shift : PAGE_SHIFT)
#define VM_MAP_PAGE_SIZE(map) (1 << VM_MAP_PAGE_SHIFT((map)))
//page_mask，取page_size-1（如size是10000，那么mask是1111）
#define VM_MAP_PAGE_MASK(map) (VM_MAP_PAGE_SIZE((map)) - 1)
#define VM_MAP_PAGE_ALIGNED(x,pgmask) (((x) & (pgmask)) == 0)
//round对齐，用当前的offset加上一个mask，相当于向上取整，进一位(offset:10010,mask:1111，那么结果就是20000)
#define vm_map_round_page(x,pgmask) (((vm_map_offset_t)(x) + (pgmask)) & ~((signed)(pgmask)))
//trunc对齐，用当前的offset向下取整(offset:10010,mask:1111，那么结果就是10000)
#define vm_map_trunc_page(x,pgmask) ((vm_map_offset_t)(x) & ~((signed)(pgmask)))
上面几个虚拟内存相关的宏定义主要就是给定一个offset，把它调整到一个页的起始位置。接下来看一下load_segment和map_segment都干了些什么。
static
load_return_t
load_segment(
struct load_command *lcp,
uint32_t filetype,
void * control,
off_t pager_offset,
off_t macho_size,
struct vnode *vp,
vm_map_t map,
int64_t slide,
load_result_t *result)
{
struct segment_command_64 segment_command, *scp;
kern_return_t ret;
size_t segment_command_size, total_section_size,
single_section_size;
vm_map_offset_t file_offset, file_size;//文件中的偏移量和大小
vm_map_offset_t vm_offset, vm_size;//load_command里定义的虚拟地址偏移量和大小
vm_map_offset_t vm_start, vm_end, vm_end_aligned;//计算得到的该段实际的开始和结束地址
vm_map_offset_t file_start, file_end;//文件中的开始和结束偏移量，根据file_offset计算得到，其实file_offset必须是4K-alignment的
//实际用的page_size 和mask，取默认PAGE_SIZE和实际map中size的最大值
vm_map_size_t effective_page_size;
vm_map_offset_t effective_page_mask;
#if __arm64__
vm_map_kernel_flags_t vmk_flags;
boolean_t fourk_align;
#endif /* __arm64__ */
effective_page_size = MAX(PAGE_SIZE, vm_map_page_size(map));
effective_page_mask = MAX(PAGE_MASK, vm_map_page_mask(map));
//xxxx…
//判断是否需要4K-alignment（4k是默认的page_size）,需要通过fourk_pager来对齐
if (LC_SEGMENT_64 == lcp->cmd) {
segment_command_size = sizeof(struct segment_command_64);
single_section_size = sizeof(struct section_64);
#if __arm64__
/* 64-bit binary: should already be 16K-aligned */
fourk_align = FALSE;
#endif /* __arm64__ */
} else {
segment_command_size = sizeof(struct segment_command);
single_section_size = sizeof(struct section);
#if __arm64__
/* 32-bit binary: might need 4K-alignment */
if (effective_page_size != FOURK_PAGE_SIZE) {
/* not using 4K page size: need fourk_pager */
fourk_align = TRUE;
verbose = TRUE;
} else {
/* using 4K page size: no need for re-alignment */
fourk_align = FALSE;
}
#endif /* __arm64__ */
}
//把lcp强转成具体命令
if (LC_SEGMENT_64 == lcp->cmd) {
scp = (struct segment_command_64 *)lcp;
} else {
scp = &segment_command;
widen_segment_command((struct segment_command *)lcp, scp);
}
//xxxxx…
//这里vm_offset用命令中指定的地址加上了之前传进来随机偏移量
vm_offset = scp->vmaddr + slide;
vm_size = scp->vmsize;
//xxxxx…
//根据是否要fourk_align来计算相应的vm_start和vm_end，本质上就是round和trunc的时候用的mask不同
#if __arm64__
if (fourk_align) {
//其实前面已经判断过file_offset是否已经是4K-alignment的了
/* 4K-align */
file_start = vm_map_trunc_page(file_offset,
FOURK_PAGE_MASK);
file_end = vm_map_round_page(file_offset + file_size,
FOURK_PAGE_MASK);
vm_start = vm_map_trunc_page(vm_offset,
FOURK_PAGE_MASK);
vm_end = vm_map_round_page(vm_offset + vm_size,
FOURK_PAGE_MASK);
if (!strncmp(scp->segname, "__LINKEDIT", 11) &&
page_aligned(file_start) &&
vm_map_page_aligned(file_start, vm_map_page_mask(map)) &&
page_aligned(vm_start) &&
vm_map_page_aligned(vm_start, vm_map_page_mask(map))) {
/* XXX last segment: ignore mis-aligned tail */
file_end = vm_map_round_page(file_end,
effective_page_mask);
vm_end = vm_map_round_page(vm_end,
effective_page_mask);
}
} else
#endif /* __arm64__ */
{
file_start = vm_map_trunc_page(file_offset,
effective_page_mask);
file_end = vm_map_round_page(file_offset + file_size,
effective_page_mask);
vm_start = vm_map_trunc_page(vm_offset,
effective_page_mask);
vm_end = vm_map_round_page(vm_offset + vm_size,
effective_page_mask);
}
//xxxxx….
//根据先前计算得到的几个偏移量，用map_segment进行映射
if (vm_size > 0) {
initprot = (scp->initprot) & VM_PROT_ALL;
maxprot = (scp->maxprot) & VM_PROT_ALL;
/*
* Map a copy of the file into the address space.
*/
ret = map_segment(map,
vm_start,
vm_end,
control,
file_start,
file_end,
initprot,
maxprot);
if (ret) {
return LOAD_NOSPACE;
}
//xxxx…….
}
return ret;
}
这里整体流程如下：
- 计算
effective_page_size和effective_page_mask，取默认值和Load Command中指定值两者中的最大值。 -
根据
effective_page_size是否等于FOURK_PAGE_SIZE来判断是否要强行通过fourk_pager来对齐。这里FOURK_PAGE_SIZE(FOURK = 4K的意思)就是4K大小，是默认的page大小。#define FOURK_PAGE_SIZE 0x1000 - 根据
effective_page_mask或者FOURK_PAGE_SIZE来trunc虚拟地址的起始值，round虚拟地址的结束值 - 用
map_segment来把文件内容（control参数里有文件的pager）映射到虚拟地址空间(map)里。 map_segment函数通过vm_map_enter_mem_object_control来向map里插入一个map_entry，把具体segment的内容映射成vm_object和vm_page。
这里涉及到了一些具体的虚拟内存的管理，只简单介绍了一些概念，后续会开新的文章详细介绍虚拟内存相关内容。
参考文献：
【1】Darwin-XNU源码：https://github.com/apple/darwin-xnu
【2】Mac OS® X and iOS Internals： http://newosxbook.com/MOXiI.pdf
【3】Mach-O Runtime Architecture: http://math-atlas.sourceforge.net/devel/assembly/MachORuntime.pdf
Image inpainting, an algorithm help you remove stamps in images
Image Inpainting
An algorithm help you remove stamps in images.
Demo
Algorithm
Image pinpointing algorithms can be mainly decided into 3 categories: structural inpainting, textural inpainting and mixed inpainting. The algorithm used in this application is a texture based inapinting algortihm[1].
General Idea
To find map between pixels in the stamp region and pixels in other parts. Then use the color of F(α) to fill pixel α.
Neighborhood matching.
Find the best pixel among candidates depends on their neighborhoods.
The “Match Rate” between origin and a candidate pixel is the Euclidian distance between them
###
In order to store the stamp region, I use pixel range of each pixel row to represent a irregular region.
Improvement
Same neighborhoods
As an example, when the algorithm is looking for the best pixel among candidates, one situation is below.
The Grey pixel is in the missing region and it’s on the circular layer 0. The blue pixel and the yellow pixel are its two possible candidates. It’s obviously that these two candidates have a big part of same neighborhoods – four green columns.
</br>
It can be a possible point where duplicate calculation happens since they have “same” neighborhoods. But are there really have duplicate calculations when calculate the Euclidian distance between these two candidates and the source pixel in the missing region? The answer is “NO”.
As an example, consider the public neighborhood pixel α. When the algorithm calculates the Euclidian distance between the blue pixel and the grey pixel, neighborhood pixel α will be compared with the pixel β. However, when it turns to the calculation of the Euclidian distance between the yellow pixel and the grey pixel, α will compare with γ.
Calculation legacy
We have already found that there are a big part of same neighborhoods between two closed candidate pixels. However, these same neighborhoods will all be compared with different pixels of neighborhoods of the source pixel in the missing region.
For each source pixel in the missing region, this algorithm will find the best candidate among those pixels near the source pixel. And for each possible pair, the algorithm should calculate the Euclidian distance between two pixels. So it becomes a time costing procedure to find out the best pixel among candidates.
As mentioned before, for one pixel in the missing region, when looking for its best candidate, there is no duplicate calculation. But how it will be if we consider more pixels in the missing region?
Considering a new pixel in the missing region. The red pixel is near the grey pixel and it’s in layer level 1. It’s obviously that the red pixel and the grey pixel have four same neighborhood columns.
</br>
When we calculate the Euclidian distance between the grey pixel and the blue pixel, pixel α will be compared with pixel β. And when we calculate the Euclidian distance between the red pixel and the yellow pixel, the pixelα will be also compared with pixel β. For all the pixels in four same neighborhood columns, calculations for the pixel in the layer level 0 are the same as those for the layer level 1. So for each pixel row in the missing region, pixels in smaller layer level can generate “calculation legacy” to pixels in bigger layer level.
</br>
It’s better to restore the calculate result of each column when implementing this feature. Since with the growth of layer level, new columns will be add in and old columns will be removed. The implementation is complicate since we need to restore different calculation legacy for each pixel row and each candidate row.
</br>