x86におけるセグメンテーションについてのメモ
書かないと忘れるので...
概要
- 16-bitマシンであった8086では20-bitのデータバスを利用するために各種セグメントレジスタの値を16bit left shiftした値+オフセットをリニアアドレスとして使用していた．*1全てのx86アーキテクチャCPUは今でも16bitリアルモードで起動する．*2
- protected modeではCPUが動作しているとき，全てのメモリアクセスはGDT(Global Descriptor Table) ，LDT(Local Descriptor Table)を経由する．
- GTD/LDTにはセグメントディスクリプタがエントリとして格納され，セグメントディスクリプタにはセグメントのベースアドレス，サイズ（limit），アクセス権限などの情報が含まれる．
- GTDレジスタとLDTレジスタにそれぞれのセグメントディスクリプタテーブルのベースアドレスが格納される．LDTはsystem segmentであるため，LDTを含むセグメントはGDTにセグメントディスクリプタを持つ必要がある．
- 32bit protected modeにおいては各種セグメントレジスタはセグメントセレクタを保持し，メモリアクセス時にはこれを参照し論理アドレスからリニアアドレスへの変換が行われている
- 64bit protected modeにおいてはセグメンテーションは基本的に無効化される．*3プロセッサが殆どの*4各種セグメントレジスタをbase: 0として取り扱うことにより64-bitのFlat Model(後述)のリニアアドレス空間が作成される．
セグメントディスクリプタの構造
(Intel® 64 and IA-32 Architectures Software Developer Manualsより)
画像に概ね書いてあるので補足だけ:
- Segment Limit: セグメントのサイズ．20bitしかないが，粒度を1Byteか4KBytesで選べるため，1B-1MiBか4KiB-4GiBの範囲で設定できる．
- G: Granularity flag．setでsegment limitを4-KiB単位の粒度に，clearなら1B単位に．
- Type: Sがsetされているときにセグメントディスクリプタがcode or dataのどちらであるか，codeならRX，コンフォーミング*5権限設定，dataならRW権限，エクスパンドダウン*6の設定を示す．
セグメントセレクタ
セグメントセレクタは各種セグメントレジスタに格納され，どのセグメントディスクリプタを参照するべきかを示す．
(Intel® 64 and IA-32 Architectures Software Developer Manualsより)
- Index: GDT/LDTのどのエントリ?
- TI: clear→GDT. set→current LDTを使う
- RPL: 要求権限レベル
実際の使われ方
セグメントディスクリプタは最低でRing0, Ring3にそれぞれコードとデータセグメント分の計4つ用意しなくてはならない（*TSSとかのsystem segmentは別として） この4つのセグメントディスクリプタをbase: 0 limit: 0xffff_ffffと設定する方法はSDMではFlat Modelとして紹介されており，xv6はFlat Modelを採用している．
以下xv6におけるGDT設定(*LDTは使われない)
void seginit(void) { struct cpu *c; // Map "logical" addresses to virtual addresses using identity map. // Cannot share a CODE descriptor for both kernel and user // because it would have to have DPL_USR, but the CPU forbids // an interrupt from CPL=0 to DPL=3. c = &cpus[cpuid()]; c->gdt[SEG_KCODE] = SEG(STA_X|STA_R, 0, 0xffffffff, 0); c->gdt[SEG_KDATA] = SEG(STA_W, 0, 0xffffffff, 0); c->gdt[SEG_UCODE] = SEG(STA_X|STA_R, 0, 0xffffffff, DPL_USER); c->gdt[SEG_UDATA] = SEG(STA_W, 0, 0xffffffff, DPL_USER); lgdt(c->gdt, sizeof(c->gdt)); }
32-bit Linuxにおいても主に使われるセグメントディスクリプタはこの4つであるが，同様にFlat Modelで設定されている．64-bit版ではbaseやlimitは意味がない． また，thread local storageなどを実現するためのセグメントディスクリプタなども別途存在し，これらはFS/GSレジスタを用いて利用される．
KVM_SET_USER_MEMORY_REGION in Linux x86 part1
Linux(tag v5.4)におけるVM ioctl KVM_SET_USER_MEMORY_REGIONリクエストの処理の流れについてのメモ．読んだ順に書いているだけなのでまとまっていない．
前提
kvmを利用したいアプリケーションはkvm APIを利用することでVMを管理するための諸構造，vCPUなどをkvmに作成してもらい，それを利用することが出来る． しかし，メモリ空間を含む仮想化されたHWはアプリケーション側が用意しなくてはならない．一般的にqemuなどがこのポジションである．
つまり，VMのゲスト物理アドレス空間とqemuなどのユーザアプリケーションの使用するホスト仮想アドレス空間のマッピングを管理する必要がある．本稿ではアプリケーションが用意したゲストメモリ空間をKVMで作成したVM上に登録，編集，削除するAPIである KVM_SET_USER_MEMORY_REGIONの挙動について記述する．
kvm APIを利用する際はまずキャラクタデバイスファイル/dev/kvmをopenすることでsystem ioctlを利用することが出来る． system ioctlではAPIバージョン，エクステンションの確認，VMの作成などを行う．
/dev/kvmにKVM_CREATE_VMリクエストを送信するとanonymous-inodeに紐付けられたファイルのfile descriptorである VM file descriptorが返され，このファイルディスクリプタ(vmfd)を用いてVM ioctlを利用できる． VM ioctlではvCPUの作成，ゲストメモリ空間の作成/編集/削除など，VM単位の操作を行う．
このvmfdに対してioctlでKVM_SET_USER_MEMORY_REGIONリクエストを発行することでゲストのメモリ空間を作成/編集/削除することができる．
KVM_CREATE_VM
まずVMを作成し，vmfdを取得するためのAPIである/dev/kvmに対するKVM_CREATE_VMリクエストについて大まかに記載する． VM ioctlの動作の詳細が本稿のメインテーマなので詳細には解説しない．
kvm_init
int kvm_init(void *opaque, unsigned vcpu_size, unsigned vcpu_align,
struct module *module)
{
（中略）
r = misc_register(&kvm_dev);
if (r) {
pr_err("kvm: misc device register failed\n");
goto out_unreg;
}
（中略）
}
miscデバイスファイルを作成する際にmiscdevice構造体kvm_devを引数に使用．
kvm_dev
static struct file_operations kvm_chardev_ops = {
.unlocked_ioctl = kvm_dev_ioctl,
.llseek = noop_llseek,
KVM_COMPAT(kvm_dev_ioctl),
};
static struct miscdevice kvm_dev = {
KVM_MINOR,
"kvm",
&kvm_chardev_ops,
};
kvmデバイスファイルのfile_operationsはkvm_chardev_ops構造体で定義されており，ioctlの処理を担う関数はunlocked_ioctlメンバのkvm_dev_ioctl関数である．
kvm_dev_ioctl
kvm_dev_ioctl in virt/kvm/kvm_main.c l3564
static long kvm_dev_ioctl(struct file *filp,
unsigned int ioctl, unsigned long arg)
{
long r = -EINVAL;
switch (ioctl) {
case KVM_GET_API_VERSION:
if (arg)
goto out;
r = KVM_API_VERSION;
break;
case KVM_CREATE_VM:
r = kvm_dev_ioctl_create_vm(arg);
break;
（中略）
out:
return r;
}
ioctlのリクエスト内容に従ってswitch, caseで分岐が行われ，kvm_dev_ioctl_create_vm関数が呼び出される．
kvm_dev_ioctl_create_vm
kvm_dev_ioctl_create_vm in virt/kvm/kvm_main.c l3500
static int kvm_dev_ioctl_create_vm(unsigned long type)
{
int r;
struct kvm *kvm;
struct file *file;
kvm = kvm_create_vm(type);
if (IS_ERR(kvm))
return PTR_ERR(kvm);
（中略）
file = anon_inode_getfile("kvm-vm", &kvm_vm_fops, kvm, O_RDWR);
if (IS_ERR(file)) {
put_unused_fd(r);
r = PTR_ERR(file);
goto put_kvm;
}
/*
* Don't call kvm_put_kvm anymore at this point; file->f_op is
* already set, with ->release() being kvm_vm_release(). In error
* cases it will be called by the final fput(file) and will take
* care of doing kvm_put_kvm(kvm).
*/
if (kvm_create_vm_debugfs(kvm, r) < 0) {
put_unused_fd(r);
fput(file);
return -ENOMEM;
}
kvm_uevent_notify_change(KVM_EVENT_CREATE_VM, kvm);
fd_install(r, file);
return r;
（中略）
}
kvm_dev_ioctl_create_vm関数は新規VMを管理するためのkvm構造体の作成，メモリスロット，IOバス割当，初期化などの処理を行い， 作成されたVMを管理するためにファイルを作成し，そのvmfdを返す． kvmを利用するアプリケーションはこのvmfdへのioctlを通じてVMを管理する．e.g. vCPUの作成，メモリ領域の作成/編集/削除など（作成されたVMはvCPUもメモリ領域も割り当てられていない) このうちメモリ領域の作成/編集/削除を担うものがKVM_SET_USER_MEMORY_REGIONである．
なお実際のkvm APIの利用フローを確かめるためにはqemuのソースコードが良い．accel/kvm/kvm-all.cから辿って読む．
KVM_SET_USER_MEMORY_REGION
kvm_dev_ioctl_create_vm関数で作成されたファイルへ登録されたfile_operations構造体はkvm_vm_fopsであるため，まずはここをチェック．
kvm_vm_fops
kvm_vm_fops in virt/kvm/kvm_main.c l3493
static struct file_operations kvm_vm_fops = {
.release = kvm_vm_release,
.unlocked_ioctl = kvm_vm_ioctl,
.llseek = noop_llseek,
KVM_COMPAT(kvm_vm_compat_ioctl),
};
unlocked_ioctlメンバからvmfdへのioctlを処理する関数はkvm_vm_ioctlであることがわかる．
kvm_vm_ioctl
kvm_vm_ioctl in virt/kvm/kvm_main.c l3263
static long kvm_vm_ioctl(struct file *filp,
unsigned int ioctl, unsigned long arg)
{
struct kvm *kvm = filp->private_data;
void __user *argp = (void __user *)arg;
int r;
if (kvm->mm != current->mm)
return -EIO;
switch (ioctl) {
case KVM_CREATE_VCPU:
r = kvm_vm_ioctl_create_vcpu(kvm, arg);
break;
case KVM_ENABLE_CAP: {
struct kvm_enable_cap cap;
r = -EFAULT;
if (copy_from_user(&cap, argp, sizeof(cap)))
goto out;
r = kvm_vm_ioctl_enable_cap_generic(kvm, &cap);
break;
}
case KVM_SET_USER_MEMORY_REGION: {
struct kvm_userspace_memory_region kvm_userspace_mem;
r = -EFAULT;
if (copy_from_user(&kvm_userspace_mem, argp,
sizeof(kvm_userspace_mem)))
goto out;
r = kvm_vm_ioctl_set_memory_region(kvm, &kvm_userspace_mem);
break;
}
（中略）
out:
return r;
}
kvm_vm_ioctl_set_memory_region関数をkvm構造体，アプリケーションから受け取ったkvm_userspace_mem構造体を渡し呼び出す．kvm_userspace_mem構造体の定義は以下の通り．
kvm_userspace_memory_region
kvm_userspace_memory_region in include/uapi/linux/kvm.h l97
/* for KVM_SET_USER_MEMORY_REGION */
struct kvm_userspace_memory_region {
__u32 slot;
__u32 flags;
__u64 guest_phys_addr;
__u64 memory_size; /* bytes */
__u64 userspace_addr; /* start of the userspace allocated memory */
};
/*
* The bit 0 ~ bit 15 of kvm_memory_region::flags are visible for userspace,
* other bits are reserved for kvm internal use which are defined in
* include/linux/kvm_host.h.
*/
#define KVM_MEM_LOG_DIRTY_PAGES (1UL << 0)
#define KVM_MEM_READONLY (1UL << 1)
各メンバは
- slot:
- 31-16: address space id．
- 15-0: slot id
- flags:
- guest_phys_addr: そのまま
- memory_size: そのまま
- userspace_addr: そのまま
kvm_vm_ioctl_set_memory_regionについて見ていく．
kvm_vm_ioctl_set_memory_region
kvm_vm_ioctl_set_memory_region in virt/kvm/kvm_main.c l1160
static int kvm_vm_ioctl_set_memory_region(struct kvm *kvm,
struct kvm_userspace_memory_region *mem)
{
if ((u16)mem->slot >= KVM_USER_MEM_SLOTS) [0]
return -EINVAL;
return kvm_set_memory_region(kvm, mem);
}
slot idがユーザスペースからアクセス可能なメモリスロット数を示すKVM_USER_MEM_SLOTS以上になっていないか調べて[0]kvm_set_memory_regionを呼ぶだけ．次はkvm_set_memory_regionについて．
kvm_set_memory_region
kvm_set_memory_region in virt/kvm/kvm_main.c l1148
int kvm_set_memory_region(struct kvm *kvm,
const struct kvm_userspace_memory_region *mem)
{
int r;
mutex_lock(&kvm->slots_lock);
r = __kvm_set_memory_region(kvm, mem);
mutex_unlock(&kvm->slots_lock);
return r;
}
ロックを獲得して__kvm_set_memory_regionを呼び出し，ロックを解放するだけ．
次は__kvm_set_memory_regionについて．長いので分割して見ていく．
__kvm_set_memory_region part1
__kvm_set_memory_region in virt/kvm/kvm_main.c l977 part1
/*
* Allocate some memory and give it an address in the guest physical address
* space.
*
* Discontiguous memory is allowed, mostly for framebuffers.
*
* Must be called holding kvm->slots_lock for write.
*/
int __kvm_set_memory_region(struct kvm *kvm,
const struct kvm_userspace_memory_region *mem)
{
int r;
gfn_t base_gfn;
unsigned long npages;
struct kvm_memory_slot *slot;
struct kvm_memory_slot old, new;
struct kvm_memslots *slots = NULL, *old_memslots;
int as_id, id;
enum kvm_mr_change change;
r = check_memory_region_flags(mem); [1]
if (r)
goto out;
~~~
check_memory_region_flags
check_memory_region_flags in virt/kvm/kvm_main.c l927
static int check_memory_region_flags(const struct kvm_userspace_memory_region *mem)
{
u32 valid_flags = KVM_MEM_LOG_DIRTY_PAGES;
#ifdef __KVM_HAVE_READONLY_MEM
valid_flags |= KVM_MEM_READONLY;
#endif
if (mem->flags & ~valid_flags)
return -EINVAL;
return 0;
}
有効なフラグ以外がmem->flagsに含まれていないか確認する[1]．
__kvm_set_memory_region part2
__kvm_set_memory_region in virt/kvm/kvm_main.c l977 part2
~~~
r = -EINVAL;
as_id = mem->slot >> 16; [2]
id = (u16)mem->slot; [3]
/* General sanity checks */
if (mem->memory_size & (PAGE_SIZE - 1)) [4]
goto out;
if (mem->guest_phys_addr & (PAGE_SIZE - 1)) [5]
goto out;
/* We can read the guest memory with __xxx_user() later on. */
if ((id < KVM_USER_MEM_SLOTS) &&
((mem->userspace_addr & (PAGE_SIZE - 1)) ||
!access_ok((void __user *)(unsigned long)mem->userspace_addr,
mem->memory_size))) [6]
goto out;
if (as_id >= KVM_ADDRESS_SPACE_NUM || id >= KVM_MEM_SLOTS_NUM) [7]
goto out;
if (mem->guest_phys_addr + mem->memory_size < mem->guest_phys_addr) [8]
goto out;
はじめに引数として受け取ったkvm_userspace_memory_region構造体について，各メンバの値の正当性の確認が行われる．
- mem->slotを16bitずつ上下に分割してas_id, idの2つに代入[2][3]．
- memory_size，guest_phys_addrに対するページサイズアライメントチェック[4]．
- slot IDがuser memory slotの範囲に収まり，かつ(userspace_addrのページサイズアライメントチェックがNGもしくはuserspace_addrからmemory_size分にアクセスできない)場合はエラーに[6]
- as_idがKVM_ADDRESS_SPACE_NUM以上である，もしくはslot IDがKMV_MEM_SLOTS_NUM以上であればエラーに[7]
- オーバーフローチェック[8]
KVM_USER_MEM_SLOTSはユーザスペースからアクセス可能なメモリ領域のスロットの数を定義している．のでslot IDがuser memory slotのものなのにuserspace_addrのアライメントが取れていなかったりuserspace_addrからmemory_size分がアクセス不能であることはおかしいということ[6]．逆にアクセス不能なメモリスロットの数はKVM_PRIVATE_MEM_SLOTSで定義され，このKVM_USER_MEM_SLOTSとKVM_PRIVATE_MEM_SLOTSを加算したものがKVM_MEM_SLOTS_NUMとして定義される．[7]はas_idがaddress spaceの数以上になっていないか，slot idが最大値(=KVM_MEM_SLOTS_NUM)を超えていないか確認しているだけ．
private slotの話をしてしまったが，そもそもioctl KVM_SET_USER_MEMORY_REGIONリクエストからこの関数を呼び出すなら，kvm_vm_ioctl_set_memory_regionの[0]でslot id >= KVM_USER_MEM_SLOTSでないことは確認しているので，privateなslotについて何も考えることはない．（KVM_SET_USER_MEMORY_REGIONだよ）
access_ok
ユーザメモリ空間がアクセス可能であるかをチェックするマクロ．であるのでアーキテクチャごとに実装が異なる．x86での定義は以下の通り． ドキュメントにあるとおり，アーキテクチャによっては指定されたメモリ空間がユーザ空間に収まっているかをチェックするだけであり，x86でもそう．
access_ok in arch/x86/include/asm/uaccess.h l76
* access_ok - Checks if a user space pointer is valid
* @addr: User space pointer to start of block to check
* @size: Size of block to check
*
* Context: User context only. This function may sleep if pagefaults are
* enabled.
*
* Checks if a pointer to a block of memory in user space is valid.
*
* Note that, depending on architecture, this function probably just
* checks that the pointer is in the user space range - after calling
* this function, memory access functions may still return -EFAULT.
*
* Return: true (nonzero) if the memory block may be valid, false (zero)
* if it is definitely invalid.
*/
#define access_ok(addr, size) \
({ \
WARN_ON_IN_IRQ(); \
likely(!__range_not_ok(addr, size, user_addr_max())); \
})
WARN_ON_IN_IRQはCONFIG_DEBUG_ATOMIC_SLEEPがyの時にのみ実体を持つ．デバッグ環境の動作までは深追いしないので__range_not_okから．
__range_not_ok
__range_not_ok in arch/x86/include/asm/uaccess.h l62
#define __range_not_ok(addr, size, limit) \
({ \
__chk_user_ptr(addr); \
__chk_range_not_ok((unsigned long __force)(addr), size, limit); \
})
__chk_user_ptrはSparseを使用する際以外は(void)0なのでスキップ．Sparseとは何？→Documentation/dev-tools/sparseを参照．
__chk_range_no_okは
return addr + size > limit
といった動作をするインライン関数であるが，その実装には工夫が見られる．別記事にして取り上げているので詳細はそちらを参照されたい．
つまり，__range_not_okはaddr + size > limitを評価し，真偽を返すマクロである．
引数limitにはaccess_okの定義内にてuser_addr_max()の返り値を渡している．
user_addr_max()はcurrent->uhread_addr_limit.segを返すマクロである．
access_okは__range_not_okの返り値の否定を返すため，その動作は
return addr + size > current->uhread_addr_limit.seg
ということになり，指定されたaddr, sizeがcurrent taskのメモリ空間内に収まっていれば真であるので，指定されたメモリ空間がユーザ空間に収まっているかのみチェックしている．
__kvm_set_memory_region part3
__kvm_set_memory_region in virt/kvm/kvm_main.c l977 part3
slot = id_to_memslot(__kvm_memslots(kvm, as_id), id); [9]
base_gfn = mem->guest_phys_addr >> PAGE_SHIFT; [10]
npages = mem->memory_size >> PAGE_SHIFT; [11]
if (npages > KVM_MEM_MAX_NR_PAGES) [12]
goto out;
new = old = *slot; [13]
new.id = id;
new.base_gfn = base_gfn;
new.npages = npages;
new.flags = mem->flags;
- as_idの正当性をチェックしつつ対応するkvm_memslots構造体を__kvm_memslots関数で求め，kvm_memslots構造体とslot idから対応するkvm_memory_slot構造体を求める[9]
- mem->guest_phys_addrをページフレームナンバーへ変換[10]
- mem->memory_sizeをページ数へ変換[11]
- ページ数がスロットに割当可能な範囲内かチェック[12]
- new, oldに[9]で得た編集したいメモリスロットに対応するkvm_memroy_slot構造体の値を代入[13]
- その後，newに引数memから得た，新しいslot id，base_gfn（メモリスロットの対応するゲスト物理アドレス空間のベースページのフレームナンバ），npages（同空間のページ数），flagsを代入
[9]のas_id，slot idに対応するkvm_memory_slot構造体を求める処理，その中で用いられる__kvm_memslots関数とid_to_memslot関数について補足するため，まずメモリスロットの構造について整理する．
struct kvm
kvm in include/linux/kvm_host.h l 443
struct kvm {
spinlock_t mmu_lock;
struct mutex slots_lock;
struct mm_struct *mm; /* userspace tied to this vm */
struct kvm_memslots __rcu *memslots[KVM_ADDRESS_SPACE_NUM];
(略)
kvm構造体はその直下にメモリスロットを編集する際に使用するロックであるmutex構造体のメンバslots_lock，各アドレススペースごとにメモリスロットを管理するためのkvm_memslots構造体の配列へのポインタmemslotsメンバを持つ．配列へのインデックスとしてas_idを使用することで各kvm_memslots構造体へアクセスできる．
slots_lockはKVM_SET_USER_MEMORY_REGIONから呼び出される場合kvm_set_memory_regionで確保されている．
struct kvm_memslots
kvm_memslots in include/linux/kvm_host.h l434
struct kvm_memslots {
u64 generation;
struct kvm_memory_slot memslots[KVM_MEM_SLOTS_NUM];
/* The mapping table from slot id to the index in memslots[]. */
short id_to_index[KVM_MEM_SLOTS_NUM];
atomic_t lru_slot;
int used_slots;
};
kvm_memslots構造体は配下にkvm_memory_slot構造体の配列であるmemslotsメンバを持つ．しかしkvm_memslots構造体のケースと異なり，kvm_memory_slot構造体の配列memslotsのインデックスはslot idではない． slot idとmemslotsのインデックスをマップする配列id_to_indexを用いてmemslotsのインデックスを得て，そのインデックスを用いて各要素にアクセスする．
struct kvm_memory_slot
kvm_memory_slot in include/linux/kvm_host.h l343
struct kvm_memory_slot {
gfn_t base_gfn;
unsigned long npages;
unsigned long *dirty_bitmap;
struct kvm_arch_memory_slot arch;
unsigned long userspace_addr;
u32 flags;
short id;
};
このkvm_memory_slot構造体がメモリスロットを表現する最小単位のデータ構造である．そのメンバは基本的にここまでで登場したデータ構造と対応するものがほとんどである． まだ登場していないdirty_bitmapはdirty trackingを実現するためのbitmap，kvm_arch_memory_slotはアーキテクチャ特有のデータを管理する構造体である．
__kvm_memslots
__kvm_memslots in include/linux/kvm_host.h l626
static inline struct kvm_memslots *__kvm_memslots(struct kvm *kvm, int as_id)
{
as_id = array_index_nospec(as_id, KVM_ADDRESS_SPACE_NUM);
return srcu_dereference_check(kvm->memslots[as_id], &kvm->srcu,
lockdep_is_held(&kvm->slots_lock) ||
!refcount_read(&kvm->users_count));
}
__kvm_memslots()はas_idが正当な値かを確認し，正当な値であればそのas_idに対応するkvm_memslots構造体のポインタをkvm構造体のメンバmemslotsから返す．
不当な値であればaddress space 0に対応するもののポインタを返す．
このas_idの正当性チェックはarray_index_nospecを用いて行われる．array_index_nospecは[0, KVM_ADDRESS_SPACE_NUM)にas_idが含まれていればas_idをそのまま返し，そうでなければ0を返す．
一見シンプルな処理であるが，高速化のために内部ではインラインアセンブリを用いた記述が行われている．詳細は以下の記事を参照されたい．
でも__kvm_set_memory_region part2の[7]でas_idがKVM_ADDRESS_SPACE_NUM以上でないかチェックしているからこの正当性チェックは意味あるのか？わからないから誰か教えてください．
id_to_memslot
id_to_memslot in include/linux/kvm_host.h l646
id_to_memslot(struct kvm_memslots *slots, int id)
{
int index = slots->id_to_index[id];
struct kvm_memory_slot *slot;
slot = &slots->memslots[index];
WARN_ON(slot->id != id);
return slot;
}
id_to_memslot()はkvm->memslotsから取得したkvm_memslots構造体のポインタから当該構造体のid_to_indexメンバを参照し，目的のメmem->userspace_addrモリスロットに対応する kvm_memslots.memslots[]のインデックスを得て，その後目的のメモリスロットのポインタを返す．
__kvm_set_memory_region part4
このパートではこれから行われるメモリスロットに対する処理の種類を決定する． 処理の種類は
- KVM_MR_CREATE: メモリスロットの作成
- KVM_MR_MOVE: メモリスロットがホスト仮想アドレス領域をマップするゲスト物理アドレス領域のベースを移動
- KVM_MR_FLAGS_ONLY: flagだけの変更
- KVM_MR_DELETE: メモリスロットの削除
の4つである．
__kvm_set_memory_region in virt/kvm/kvm_main.c l977 part4
if (npages) {
if (!old.npages)
change = KVM_MR_CREATE;
else { /* Modify an existing slot. */
if ((mem->userspace_addr != old.userspace_addr) ||
(npages != old.npages) ||
((new.flags ^ old.flags) & KVM_MEM_READONLY))
goto out;
if (base_gfn != old.base_gfn)
change = KVM_MR_MOVE;
else if (new.flags != old.flags)
change = KVM_MR_FLAGS_ONLY;
else { /* Nothing to change. */
r = 0;
goto out;
}
}
} else {
if (!old.npages)
goto out;
change = KVM_MR_DELETE;
new.base_gfn = 0;
new.flags = 0;
}
メモリスロットに対する操作の判定は以下のように行われる．
- npagesが0でない
- old.npagesが0
- 当該メモリスロットはまだ利用されていないので操作はメモリスロットの作成となる
- old.npagesが0でない
- (mem->userspace_addr != old.userspace_addr) || (npages != old.npages) || ((new.flags ^ old.flags) & KVM_MEM_READONLY) true
- (mem->userspace_addr != old.userspace_addr) || (npages != old.npages) || ((new.flags ^ old.flags) & KVM_MEM_READONLY) false
- base_gfn != old.base_gfn
- メモリスロットに対する操作はマップ先のゲスト物理アドレス空間のベースの移動
- base_gfn == old.base_gfn
- new.flags != old.flags
- メモリスロットに対する操作はフラッグの変更
- new.flags == old.flags
- やることなし
- new.flags != old.flags
- base_gfn != old.base_gfn
- old.npagesが0
- npagesが0
- old.npagesが0
- エラー．まだ使用されていないスロットに対して削除を行うことになる．
- old.npagesが0でない
- メモリスロットに対する操作は削除になる．このときnew.npagesは既に0であるので，残りのbase_gfn，flagsも0とする
- old.npagesが0
__kvm_set_memory_region part5
if ((change == KVM_MR_CREATE) || (change == KVM_MR_MOVE)) { [14]
/* Check for overlaps */
r = -EEXIST;
kvm_for_each_memslot(slot, __kvm_memslots(kvm, as_id)) {
if (slot->id == id)
continue;
if (!((base_gfn + npages <= slot->base_gfn) ||
(base_gfn >= slot->base_gfn + slot->npages)))
goto out;
}
}
/* Free page dirty bitmap if unneeded */
if (!(new.flags & KVM_MEM_LOG_DIRTY_PAGES)) [15]
new.dirty_bitmap = NULL;
r = -ENOMEM;
if (change == KVM_MR_CREATE) { [16]
new.userspace_addr = mem->userspace_addr;
if (kvm_arch_create_memslot(kvm, &new, npages))
goto out_free;
}
/* Allocate page dirty bitmap if needed */
if ((new.flags & KVM_MEM_LOG_DIRTY_PAGES) && !new.dirty_bitmap) { [17]
if (kvm_create_dirty_bitmap(&new) < 0)
goto out_free;
}
- [14]は書いてあるとおりKVM_MR_CREATE || KVM_MR_MOVEのときの処理．as_idに対応するkvm_memslots構造体中のメンバmemslotsの各kvm_memory_slot構造体についてイテレーションを行い，現在作成，移動しようとしているメモリスロットのマップ先ゲスト物理アドレス空間が既存のメモリスロットのマップ先と重複しないかチェック．重複していたら-EEXISTを返す．
- [15]でもしnew.flagsにKVM_MEM_LOG_DIRTY_PAGESが含まれていないならnew.dirty_bitmapをクリアしておく．
- [16]でメモリスロットに対する操作がKVM_MR_CREATEであればnew.userspace_addrにmem->userspace_addrを代入し，kvm_arch_create_memslotをコールする．この関数の内部では基本必要なデータ構造をkvcallocでアロケートしていくので，失敗したら-ENOMEM
- [17]でもしnew.flagsにKVM_MEM_LOG_DIRTY_PAGESが立っていてかつnew.dirty_bitmapが存在しない状況であればkvzallocでdirty bitmap領域をアロケートする．dirty bitmapはbitmapを用いてdirty trackingを実現するための仕組みであるが，これについて詳細に書くと別方式のdirty ringについても書かなきゃいけないので書かない．内部では基本dirty bitmapの領域のアロケートが行われているので失敗したら-ENOMEM．後でdirty bitmap / ringの記事も作りたいな...
[17]のdirty bitmapについては本稿で解説しないので，[16]のkvm_arch_create_memslotについて詳しく見ていく．
kvm_arch_create_memslot
コード中にlpageという単語が多く出てくるが，これはlarge pageのことである．これだけ頭に留めておくとスッと読める．
kvm_arch_create_memslot in arch/x86/kvm/x86.c l9646
int kvm_arch_create_memslot(struct kvm *kvm, struct kvm_memory_slot *slot,
unsigned long npages)
{
int i;
for (i = 0; i < KVM_NR_PAGE_SIZES; ++i) { [18]
struct kvm_lpage_info *linfo;
unsigned long ugfn;
int lpages;
int level = i + 1;
lpages = gfn_to_index(slot->base_gfn + npages - 1,
slot->base_gfn, level) + 1; [19]
slot->arch.rmap[i] =
kvcalloc(lpages, sizeof(*slot->arch.rmap[i]),
GFP_KERNEL_ACCOUNT); [20]
if (!slot->arch.rmap[i])
goto out_free;
（略）
はじめにKVM_NR_PAGE_SIZES回のループが行われる[18]．この定数&関連する定数の定義は以下の通り．
KVM_NR_PAGE_SIZES
KVM_NR_PAGE_SIZES in arch/x86/include/asm/kvm_host.h l104
/* KVM Hugepage definitions for x86 */
enum {
PT_PAGE_TABLE_LEVEL = 1,
PT_DIRECTORY_LEVEL = 2,
PT_PDPE_LEVEL = 3,
/* set max level to the biggest one */
PT_MAX_HUGEPAGE_LEVEL = PT_PDPE_LEVEL,
};
#define KVM_NR_PAGE_SIZES (PT_MAX_HUGEPAGE_LEVEL - \
PT_PAGE_TABLE_LEVEL + 1)
従ってKVM_NUR_PAGE_SIZESの値は3-1+1=3となり，[18]では3回のループが行われる．
その後いくつか変数の宣言が行われ，[19]でgfn_to_indexを呼び出され，結果に1を足した値がlpagesに格納される．
ここでは各ページサイズを使用したときにゲスト物理アドレス空間を表すために必要なページ数を計算する．
gfn_to_indexの詳細を追う．
gfn_to_index
gfn_to_index in arch/x86/include/asm/kvm_host.h l120
gfn_to_indexの定義
static inline gfn_t gfn_to_index(gfn_t gfn, gfn_t base_gfn, int level)
{
/* KVM_HPAGE_GFN_SHIFT(PT_PAGE_TABLE_LEVEL) must be 0. */
return (gfn >> KVM_HPAGE_GFN_SHIFT(level)) -
(base_gfn >> KVM_HPAGE_GFN_SHIFT(level));
}
KVM_HPAGEGFN_SHIFTは以下のように定義される．
#define KVM_HPAGE_GFN_SHIFT(x) (((x) - 1) * 9)
9でピンと来る人が多いと思うが，gfn >> KVM_HPAGE_GFN_SHIFT()は各ページテーブル構造の階層に応じてフレームナンバをページテーブル構造のインデックスに変換していることになる．これはページサイズに応じて，とも言いかえられる．
e.g.
- ページテーブル(level=1)内のエントリのインデックス
= gfn >> 0 (=((1-1)*9)) -> ページサイズ4KiB (2^12)
- ページディレクトリ(level=2)内のエントリのインデックス
= gfn >> 9 (=((2-1)*9)) -> ページサイズ2MiB(2^12*2^9)
- ページディレクトリポインタポインタテーブル(level=3)内のエントリのインデックス
= gfn >> 18 (=((3-1)*9)) -> ページサイズ1GiB(2^12*2^9*2^9)
その後，[20]でkvm_memory_slot.arch.rmap[i]にlpages*sizeof(*slot->arch.rmap[i])分のメモリを確保している．
rmapはgfnに対応するpte_listをページサイズごとに格納するデータ構造であり，kvm_memory_slot構造体のメンバarchであるkvm_arch_memory_slot構造体の中に定義されている．
rmapがあることでホストはゲストの使用するページを効率的に追跡できる．例えばゲスト物理メモリ空間はホストから見るとqemuなどのユーザアプリケーションのメモリ空間であるため，当然swap-outされることがある．このとき，kvm側でEPTなどのエントリを編集しなければならないが，rmapがgfn<->pteの参照を可能にしていると，無駄なページウォークなくこれが実現できる．
kvm_arch_memory_slot構造体の定義を見ていく．
struct kvm_arch_memory_slot
kvm_arch_memory_slot in arch/x86/include/asm/kvm_host.h l794
struct kvm_arch_memory_slot {
struct kvm_rmap_head *rmap[KVM_NR_PAGE_SIZES];
struct kvm_lpage_info *lpage_info[KVM_NR_PAGE_SIZES - 1];
unsigned short *gfn_track[KVM_PAGE_TRACK_MAX];
};
kvm_rmap_head in arch/x86/include/asm/kvm_host.h l308
struct kvm_rmap_head {
unsigned long val;
};
要素数がKVM_NR_PAGE_SIZESであること，[20]でkvm_memory_slot.arch.rmap[i]にlpages*sizeof(*slot->arch.rmap[i])=lpages*sizeof(struct kvm_rmap_head)分のメモリ空間をアロケートしていることから，
rmapは各ページサイズ数分，”メモリスロットがマップするメモリ空間のページ数個の要素を持つkvm_rmap_head構造体の配列”，へのポインタを持つ配列であることがわかる．kvm_rmap_headにはpte_listへのポインタが格納され，gfn<->pteの参照を実現する．
Memo ioctl? unlocked_ioctl? compat_ioctl?
unlocked_ioctlメンバは通常のioctl処理を記載．compat_ioctlメンバには32bit systemcallからの呼び出し時の処理を記載する． 32bit ABIでビルドされたアプリを32bit ABIを有効にしてビルドしたLinuxで実行した際などに使用される．
array_index_nospec in Linux x86
Linux(tag v5.4)のソースコードリーディングをしていたときに面白いと思ったマクロのメモ．
array_index_nospec
include/linux/nospec.hで以下のように定義される．
/*
* array_index_nospec - sanitize an array index after a bounds check
*
* For a code sequence like:
*
* if (index < size) {
* index = array_index_nospec(index, size);
* val = array[index];
* }
*
* ...if the CPU speculates past the bounds check then
* array_index_nospec() will clamp the index within the range of [0,
* size).
*/
#define array_index_nospec(index, size) \
({ \
typeof(index) _i = (index); \
typeof(size) _s = (size); \
unsigned long _mask = array_index_mask_nospec(_i, _s); \
\
BUILD_BUG_ON(sizeof(_i) > sizeof(long)); \
BUILD_BUG_ON(sizeof(_s) > sizeof(long)); \
\
(typeof(_i)) (_i & _mask); \
})
コメントにある通り，このマクロは配列のインデックス，サイズをそれぞれ引数index，sizeとして取り，indexがsize-1を超過していないかチェックする．
もし超過していればidxを[0, size)の範囲に固定して（具体的には0を）返す．
実装としては引数indexを_l，sizeを_sに代入した後，array_index_mask_nospec()の引数として渡し，戻り値を_maskに代入し，
その後，_l &_maskを返す．
x86においてはarray_index_mask_nospec()はarch/x86/include/asm/barrier.hに以下のように定義される．
/**
* array_index_mask_nospec() - generate a mask that is ~0UL when the
* bounds check succeeds and 0 otherwise
* @index: array element index
* @size: number of elements in array
*
* Returns:
* 0 - (index < size)
*/
static inline unsigned long array_index_mask_nospec(unsigned long index,
unsigned long size)
{
unsigned long mask;
asm volatile ("cmp %1,%2; sbb %0,%0;"
:"=r" (mask)
:"g"(size),"r" (index)
:"cc");
return mask;
}
array_index_mask_nospec()はインラインアセンブリで定義される．ここで実行されるアセンブリは以下のようになる．
cmp size, index; sbb mask, mask;
cmp命令は減算index - sizeを行いフラグをセットするため，indexが正常値のときはCFがセットされる．
sbb命令は第一オペランドから第二オペランドとCFを減算するため，indexが正常値のときはmaskに0UL-1UL=ULONG_MAXを，indexが配列のサイズを超えているときはmaskに0をセットする．
その後，array_index_nospecは_i & _maskをreturnする．
i.e. インデックスが配列のサイズを超えている時はindexは0とのビット論理積=0を返し，インデックスが正常値のときはindexとULONG_MAXとの論理積=indexを返す．
ありがちな処理が軽量なバイナリとなるように配慮されて実装されていることがわかる．恐らくこう書くとconditional jumpとかが消えるんじゃないかな．知らんけど．
__chk_range_not_ok() in Linux x86
Linux(tag v5.4)のソースコードリーディングをしていたときに面白いと思った関数のメモ．
__chk_range_not_ok()
arch/x86/include/asm/uaccess.hにて以下のように定義される．
static inline bool __chk_range_not_ok(unsigned long addr, unsigned long size, unsigned long limit)
{
/*
* If we have used "sizeof()" for the size,
* we know it won't overflow the limit (but
* it might overflow the 'addr', so it's
* important to subtract the size from the
* limit, not add it to the address).
*/
if (__builtin_constant_p(size)) [1]
return unlikely(addr > limit - size); [2]
/* Arbitrary sizes? Be careful about overflow */
addr += size; [3]
if (unlikely(addr < size))
return true;
return unlikely(addr > limit);
}
この関数の動作は符号なし整数型のサイズを無視して記述すればreturn addr + size > limitである．
しかし，Cコードの世界ではwrap aroundを考慮して記述しなければならない．(addr + sizeがwrap aroundする可能性がある)
愚直に実装するのであれば[3]以下のようにaddrにsizeを加算しwrap aroundをチェック．
wrap aroundすれば0を返す．wrap aroundしなければreturn addrにsizeを加算した値 > limitすればよい．
この関数ではコンパイラの組み込み関数である__builtin_constant_p()を用いることで関数の高速化を図っている[1]．
__builtin_constant_p()は引数に数値を取り，引数がコンパイル時に定数であること(constant-flodingされた場合なども含む)を証明できれば1，出来なければ0を返す．(戻り値0は定数でないことを意味しない，定数と証明できないことを意味する)
その場合はsize > limitとならないように実装されているため，limit - sizeはwrap aroundを起こさない．
よって[2]のように比較を行うことが可能である．
定数であることを判別できない場合はオーソドックスにwrap aroundのチェックを行ってから比較を行う．
ABC099 C問題: とりあえずDPは良くない?
教育的な内容だったのでメモ.
詳細は上記リンクより参照.
問題の概要:
1<=N<=100000 Nは整数
であるときにN円を支払いたいとする. 一回に支払える金額は
1円 6円, 6^2円, 6^3円, ... 9円, 9^2円, 9^3円, ...
のいずれかである.
この制約下で合計N円を支払う時に少なくとも必要な支払いの数を求める.
何も考えずに以下の考え方でDPを適用してもO(NlogN)だけど...
合計N円を支払う際に必要な支払いの回数をf(N)とすると f(N) = min(f(N-1), f(N-6), f(N-6^2), f(N-6^3), ... , f(N-9), f(N-9^2), f(N-9^3), ... )
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <valarray>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// namespace
using namespace std;
// type
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using PAIR = pair<int, int>;
using PAIRLL = pair<ll, ll>;
// input
#define INIT ({ ios::sync_with_stdio(false); cin.tie(0); })
#define VAR(type, ...) type __VA_ARGS__; var_scan(__VA_ARGS__);
template<typename T>
static void var_scan(T& t)
{
cin >> t;
}
template<typename T, typename... R>
static void var_scan(T& t, R&... rest)
{
cin >> t;
var_scan(rest...);
}
// output
#define OUT(var) cout << (var)
#define SPC cout << ' '
#define TAB cout << '\t'
#define BR cout << '\n'
#define ENDL cout << endl
#define FLUSH cout << flush
// debug
#ifdef DEBUG
#define EPRINTF(fmt, ...) fprintf(stderr, fmt, __VA_ARGS__)
#define DUMP(var) cerr << #var << '\t' << (var) << '\n'
#define DUMPITERABLE(i) do { \
cerr << #i << '\t'; \
for (const auto& it : i) { cerr << it << ' '; } \
cerr << '\n'; \
} while (0)
#define DUMPITERABLE2(i2) do { \
cerr << #i2 << '\t'; \
for (const auto& it : i2) { \
for (const auto& it2: it) { \
cerr << it2 << ' '; \
} \
} \
cerr << '\n'; \
} while (0)
#else
#define EPRINTF(fmt, ...)
#define DUMP(var)
#define DUMPITERABLE(i)
#define DUMPITERABLE2(i)
#endif
// util
// [l, r)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define FOR(i, l, r) for (int i = (l); i < (r); i++)
#define RFOR(i, r, l) for (int i = (r)-1; i >= (l); i--)
#define REPLL(i, n) for (ll i = 0; i < (n); i++)
#define RREPLL(i, n) for (ll i = (n)-1; i >= 0; i--)
#define FORLL(i, l, r) for (ll i = (l); i < (r); i++)
#define RFORLL(i, r, l) for (ll i = (r)-1; i >= (l); i--)
static ll dparr[100000+1] = {0};
static PAIRLL get_maxe(ll n)
{
ll maxe_6 = 0;
ll maxe_9 = 0;
while (true) {
if (n < pow(6, maxe_6)) {
maxe_6--;
break;
} else {
maxe_6++;
}
}
while (true)
if (n < pow(9, maxe_9)) {
maxe_9--;
break;
} else {
maxe_9++;
}
return make_pair(maxe_6, maxe_9);
}
static ll dp(ll n)
{
PAIRLL maxe = get_maxe(n);
ll sub;
vector<ll> minvec;
FORLL(i, 1, maxe.second+1) {
sub = pow(9,i);
if (n-sub == 0)
goto zero;
if (!dparr[n-sub])
dparr[n-sub] = dp(n-sub);
minvec.push_back(dparr[n-sub]);
}
FORLL(i, 1, maxe.first+1) {
sub = pow(6,i);
if (n-sub == 0)
goto zero;
if (!dparr[n-sub])
dparr[n-sub] = dp(n-sub);
minvec.push_back(dparr[n-sub]);
}
if (n-1 == 0)
goto zero;
if (!dparr[n-1])
dparr[n-1] = dp(n-1);
minvec.push_back(dparr[n-1]);
return (*min_element(minvec.begin(), minvec.end()))+1;
zero:
return 1;
}
int main(void)
{
INIT;
VAR(ll, n);
OUT(dp(n));
ENDL;
return 0;
}
しかし, 一回の支払いの単位が1円 (e.g. 60 or 90), 6n円, 9n円に限られていることに注目すると, 以下の考え方でも解ける.
3通りに場合分け 1. 6^0円 or 6^n円のみで支払う場合→Nを6進数に変換し, 各桁の数字の合計を取る 2. 9^0円 or 9^n円のみで支払う場合→Nを9進数に変換し, 各桁の数字の合計を取る 3. 1円, 6^n円, 9^n円を使い支払う場合→Nを6の累乗円で支払う部分, 9の累乗円で支払う部分に分けて全探索 各々の値のうち最小値が答え.
面白い...
ABC179 E問題: 数列の各項の剰余における周期性
詳細は上記リンクより参照.
問題の概要:
1 <= N <= 10^10 0 <= X < M <= 10^5 N, X, Mはそれぞれ整数
という制約下において,
初期値: A_1 = X 漸化式: A_(n+1) = (A_n)^2 mod M
で定義される数列Aについて,
A_1からA_Nまでの各項の和を求めるというもの.
この手の問題によく触れている人ならば数列の定義を見た瞬間, 項に周期性があることは想像できる.
周期性を持つ根拠を簡単に説明すると, 以下のようになる.
数列Aの定義より, Aの各項は高々M通り(0, ... , M-1).
よって鳩の巣原理より, A_1からA_(M+1)までの各項には同じ値を持つ2項が必ず存在する.
この2項をそれぞれA_(n1), A_(n2) (n1<n2) とする.
ここで, 数列Aの定義より,
A_(n1) = A_(n2) であるならば, A_(n1+1) = (A_(n1))^2 mod M = (A_(n2))^2 mod M = A_(n2+1) 同様にして, A_(n1+2) = A_(n2+2) A_(n1+3) = A_(n2+3) ...
よって, n1個目以上である数列Aの各項において
A_n = A_(n+n2-n1) (n>=n1)
である. これは数列Aの各項がn1個目以上においてループし, その周期はn2-n1であることを意味している.
実装方法については, 愚直に最大M+1回 数列Aの各項を計算しループを検出する, ダブリングを用いる, などが考えられるが, 制約上Mは最大10^5であるため計算量には余裕があると判断したことから, シンプルに実装することを選んだ.
ループの周期は自由に選んで問題ないので, 数列Aの各項をM+1個計算し, A_(M+1)のインデックスをn2, A_(M+1)と一致する値を持つ最も後ろの項のインデックスをn1とし, 数列Aを
- ループ開始前
- ループ部
- ループ部が終了するまえに
N項目に達する部分
の3通りに分けて計算した.
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <valarray>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// namespace
using namespace std;
// type
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using PAIR = pair<int, int>;
using PAIRLL = pair<ll, ll>;
// input
#define INIT ({ ios::sync_with_stdio(false); cin.tie(0); })
#define VAR(type, ...) type __VA_ARGS__; var_scan(__VA_ARGS__);
template<typename T>
static void var_scan(T& t)
{
cin >> t;
}
template<typename T, typename... R>
static void var_scan(T& t, R&... rest)
{
cin >> t;
var_scan(rest...);
}
// output
#define OUT(var) cout << (var)
#define SPC cout << ' '
#define TAB cout << '\t'
#define BR cout << '\n'
#define ENDL cout << endl
#define FLUSH cout << flush
// debug
#ifdef DEBUG
#define EPRINTF(fmt, ...) fprintf(stderr, fmt, __VA_ARGS__)
#define DUMP(var) cerr << #var << '\t' << (var) << '\n'
#define DUMPITERABLE(i) do { \
cerr << #i << '\t'; \
for (const auto& it : i) { cerr << it << ' '; } \
cerr << '\n'; \
} while (0)
#define DUMPITERABLE2(i2) do { \
cerr << #i2 << '\t'; \
for (const auto& it : i2) { \
for (const auto& it2: it) { \
cerr << it2 << ' '; \
} \
} \
cerr << '\n'; \
} while (0)
#else
#define EPRINTF(fmt, ...)
#define DUMP(var)
#define DUMPITERABLE(i)
#define DUMPITERABLE2(i)
#endif
// util
// [l, r)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define FOR(i, l, r) for (int i = (l); i < (r); i++)
#define RFOR(i, r, l) for (int i = (r)-1; i >= (l); i--)
#define REPLL(i, n) for (ll i = 0; i < (n); i++)
#define RREPLL(i, n) for (ll i = (n)-1; i >= 0; i--)
#define FORLL(i, l, r) for (ll i = (l); i < (r); i++)
#define RFORLL(i, r, l) for (ll i = (r)-1; i >= (l); i--)
int main(void)
{
INIT;
// 1<= n <= 10^10
// 0 <= x < m <= 10^5
VAR(ll, n, x, m);
ll an = x, n1, n2, sum = 0LL, lsum, rest;
vector<ll> a;
a.push_back(an);
REPLL(i, m) { // a[1], ..., a[m]
an = (ll)pow(an,2) % m;
a.push_back(an);
}
n2 = m;
REPLL(i, m) // a[0], ..., a[m-1]
if (a[i] == a[m])
n1 = i;
if (n <= m+1) {
sum += accumulate(a.begin(), a.begin()+n, 0LL);
} else {
sum += accumulate(a.begin(), a.begin()+n1, 0LL);
lsum = accumulate(a.begin()+n1, a.begin()+n2, 0LL);
rest = accumulate(a.begin()+n1, a.begin()+n1+(n-n1)%(n2-n1), 0LL);
sum += lsum*((n-n1)/(n2-n1));
sum += rest;
}
OUT(sum);
ENDL;
return 0;
}
ProtonMail: プライバシーポリシー Memo
周りの人がProtonはいいというが何が具体的に良いのかは調べないとわからないので，プライバシーポリシー, それに関連する文書を読んだ際の備忘録的なメモ.
あくまで著者自身用のメモであり, 内容の正確性は一切保証できない. 現在の内容は 2022/03/06 時点での情報に基づく.
興味深かったことは ProtonMail がドイツにもサーバを配置しているということ . Wikipedia には以下のようにあるが
ProtonMailはサードパーティーのサーバーを使わず、すべてのサーバーはスイス国内のローザンヌとアティングハウゼン（ドイツ語版、英語版）に設置されている。
プライバシーポリシーにはこのように記載されている.
All servers used in connection with the provisioning of the Services are located in Switzerland and Germany and wholly owned and operated by the Company.
深く調べられていないが, Reddit への投稿で将来的な DC のロケーションについて意見を求めており, アムステルダムとフランクフルトの2候補が挙がっていたようなので, フランクフルトに設置されたのだろうか?
求人情報にもフランクフルトでの求人が紹介されている.
- 準拠法
- アカウント開設に関連するデータ
- データの収集
- データの保持
- データの使用
- データストレージ
- サードパーティネットワーク
- データサブプロセッサ
- データの開示
- アクセス権, 訂正権, 消去権, データポータビリティ権, 監査機関に対する不服申し立て権
- プライバシーポリシーの改訂
- 参考:
準拠法
- スイス
アカウント開設に関連するデータ
Waiting list, Email verification, notification/recovery email
- DPA の定義する個人情報として解釈し, 同法に基づいて保護される
- この情報は以下の目的にのみ使用される
- サービスに関する重要な情報の通知
- セキュリティに関する情報の通知
- アカウント作成用リンクの送信
- アカウントの承認
- パスワードリカバリー
- その他の Proton 製品の情報
- これらの機能はいつでも opt-out 可能である
Human Verification においてユーザが入力するデータ
ProtonMail が提供する Human Verification の手段は以下の3つ.
- CAPTCHA
- SMS
これらはアカウント作成時のみでなく, 重要な操作を行う場合にも要求される場合がある.
しかし, Human Verification のフェーズにおいて必ずこの3つの選択肢が提示されるわけではない. 複数のアカウントを作成しようとした場合, Spammer, Attacker である可能性が高いと判断された場合には Email, SMS を用いて Human Verification を行うことが要求される模様.
- CAPTCHA の結果は保存されない
- IPアドレス, メールアドレス, 電話番号が一時的に保存される
- 保存される期間はスパム対策のために適切と判断される期間, または適用法に準拠した期間である
- データが永久に保存される場合は必ずハッシュ化される
- メールアドレス, 電話番号はハッシュ化された上でアカウントに紐付けられる
- これらのハッシュは永久に紐付けられることはない
- ハッシュが紐付けられる期間は明示されていない
データの収集
大部分を省略, クリティカルな部分を抜粋.
Web サイトへの訪問
- オープンソースの分析ツールをローカルにインストール
- 分析結果は可能な限り匿名化され, ローカルにのみ保存される
- (ここでのローカルは NOT cloud を意味している)
- ProtonMail は Matomo を用いてアクセス解析を行っている
IP ロギング
- デフォルトではユーザのサービス利用に関する永久的な IP ロギングは行わない
- 悪用, 不正防止のために一時的に IP ログを保持することがある
- 利用規約に違反するアクティビティに従事した場合 (スパム, ProtonMail のインフラに対する DDoS, ブルートフォース, etc.) IP ログが永久に保持されることがある
- ユーザがスイスの法律に違反する場合, ProtonMailは 法的に IP アドレスの記録を強制される場合がある (これは ProtonVPN には適用されない)
- ユーザが認証ログを有効にしている場合, 自身で削除しない限り, ログインに使用された IP アドレスは永久に保存される
決済手段情報
ネイティブアプリケーション
- ネイティブアプリを使用する場合, Proton Technologies AG と モバイルアプリのプラットフォームプロバイダはプライバシーポリシーの他の箇所で言及されている情報に加えて, 特定の情報を収集できる
- Proton Technologies AG はモバイル分析ソフトウェア (fabric.io app, statistics and crash reporting, Play Store app statistics, App Store app statistics, or self-hosted Sentry crash reporting) を利用し, クラッシュレポートなどを送信することができる
- Google Play Store, Apple App Store などでは, 最も使用されているデバイス, インストール数, アンインストール数, アクティブユーザ数などの情報を収集し, それぞれの利用規約によって管理することができる
- ProtonMail はユーザのデバイスにプッシュ通知を送信するためにデバイス ID にアクセスできる
- Proton Technologies AG のアプリが位置情報にアクセス, 追跡することはない
- 収集された個人データは全て匿名化される
Import Assistant
データを移行するため Import assistant を使用する際には2つのオプションがある
Sign in with Google
Username and Password
- その他のサービスプロバイダのメールアカウントのクレデンシャルを用いる
- 移行の終了時にこれらのクレデンシャルは完全に削除される
データの保持
アカウントが削除された際, データは:
- プロダクションサーバから直ちに削除される
- 削除から30日以内の間はバックアップされている可能性がある
データの使用
- データの開示に記載された条件下以外でデータが共有されることはない
- 以下の例外を除き、データの解析を行うことはない. どちらもスパムメールを検知するため.
- 暗号化されていないメッセージを受信した場合
- 解析後, メッセージは暗号化され保存される
- 解析後, Proton Technologies AG がメッセージにアクセスする手段はない
- 暗号化を無効化して外部のメールサービスに送信されたメッセージ
- 暗号化されていないメッセージを受信した場合
データストレージ
- サービスの提供に関わり使用される全サーバはスイス, ドイツに所在し, Proton Technologies AG が100%所有するものである
- Proton Technologies AG の従業員のみが物理的, その他の手段によりアクセス可能である
- データは常に暗号化され保存される
- 定期的にオフラインのバックアップが作成されるが, これも暗号化される
サードパーティネットワーク
- Proton アプリ (Webクライアントは含まれない) にはalternative routingが実装されており, Proton サービスがブロックされていると判断した場合に Proton Technologies AG が管理しないNWを通じて Proton サービスへのアクセスを実現する
- これにより, 第三者がユーザの IP アドレス, ユーザが Proton サービスを利用していることを把握できる
- Alternative routing はオプションであり, 無効にすることができる
データサブプロセッサ
Zendesk
- カスタマーサポートに関するデータの処理を提供
- Zendesk に提供されるデータはユーザがサポートチケットに含めたもののみ
データの開示
- スイス当局からの法的義務を伴う要求があった場合のみ開示を行う
- 電子的な要求に応じることがあるが, そのデータは裁判所命令の原本を受領し, 正式な回答を提供した後にのみ法定で有効
- 暗号化されたデータの提供を要求され, 解読する能力を持たない場合, 暗号化されたデータを提供することができる
- 法律で認められている場合, データの開示の前にユーザに連絡する
- スイスの法律ではデータ要求の対象者に通知をすることが定められている
- この通知は当局から行われる場合がある
- 公共の利益がある場合, データ要求に異議を唱える場合がある
- この場合, 全ての法的, 救済措置が完了するまでデータ要求に応じない
- ただし, GDPR, スイスの法律により, 攻撃に対する防御を目的としたデータの開示は認められる
アクセス権, 訂正権, 消去権, データポータビリティ権, 監査機関に対する不服申し立て権
プライバシーポリシー内にあるデータ主体権のうち4つ (NOT 5) と1を題にした項目.
内容は
- Proton Technologies AG が処理したデータを, ユーザはサービス経由でアクセス, 編集, 削除, エクスポートすることができる
- アカウントが凍結されている場合はサポートにリクエストを送ることでこれらの操作を実行できる
- これらの権利が侵害された場合, 監査機関に不服を申し立てることができる
プライバシーポリシーの改訂
- 改訂はブログ上で通知される
- サービスを継続的に使用することで改訂に同意したと見做される
