1/*
2 * Copyright (C) 2013 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include <errno.h>
18#include <fcntl.h>
19#include <getopt.h>
20#include <inttypes.h>
21#include <stdbool.h>
22#include <stdint.h>
23#include <stdlib.h>
24#include <string.h>
25#include <sys/types.h>
26#include <unistd.h>
27
28#include <pagemap/pagemap.h>
29
30#define MAX_FILENAME  64
31
32#define GROWTH_FACTOR 10
33
34#define NO_PATTERN    0x100
35
36#define PR_SORTED       1
37#define PR_VERBOSE      2
38#define PR_ALL          4
39
40struct vaddr {
41    unsigned long addr;
42    size_t num_pages;
43    pid_t pid;
44};
45
46struct ksm_page {
47    uint64_t count;
48    uint32_t hash;
49    struct vaddr *vaddr;
50    size_t vaddr_len, vaddr_size;
51    size_t vaddr_count;
52    uint16_t pattern;
53};
54
55struct ksm_pages {
56    struct ksm_page *pages;
57    size_t len, size;
58};
59
60static void usage(char *myname);
61static int getprocname(pid_t pid, char *buf, int len);
62static int read_pages(struct ksm_pages *kp, pm_map_t **maps, size_t num_maps, uint8_t pr_flags);
63static void print_pages(struct ksm_pages *kp, uint8_t pr_flags);
64static void free_pages(struct ksm_pages *kp, uint8_t pr_flags);
65static bool is_pattern(uint8_t *data, size_t len);
66static int cmp_pages(const void *a, const void *b);
67extern uint32_t hashword(const uint32_t *, size_t, int32_t);
68
69int main(int argc, char *argv[]) {
70    pm_kernel_t *ker;
71    pm_process_t *proc;
72    pid_t *pids;
73    size_t num_procs;
74    size_t i;
75    pm_map_t **maps;
76    size_t num_maps;
77    char cmdline[256]; // this must be within the range of int
78    int error;
79    int rc = EXIT_SUCCESS;
80    uint8_t pr_flags = 0;
81    struct ksm_pages kp;
82
83    memset(&kp, 0, sizeof(kp));
84
85    opterr = 0;
86    do {
87        int c = getopt(argc, argv, "hvsa");
88        if (c == -1)
89            break;
90
91        switch (c) {
92            case 'a':
93                pr_flags |= PR_ALL;
94                break;
95            case 's':
96                pr_flags |= PR_SORTED;
97                break;
98            case 'v':
99                pr_flags |= PR_VERBOSE;
100                break;
101            case 'h':
102                usage(argv[0]);
103                exit(EXIT_SUCCESS);
104            case '?':
105                fprintf(stderr, "unknown option: %c\n", optopt);
106                usage(argv[0]);
107                exit(EXIT_FAILURE);
108        }
109    } while (1);
110
111    error = pm_kernel_create(&ker);
112    if (error) {
113        fprintf(stderr, "Error creating kernel interface -- "
114                        "does this kernel have pagemap?\n");
115        exit(EXIT_FAILURE);
116    }
117
118    if (pr_flags & PR_ALL) {
119        error = pm_kernel_pids(ker, &pids, &num_procs);
120        if (error) {
121            fprintf(stderr, "Error listing processes.\n");
122            exit(EXIT_FAILURE);
123        }
124    } else {
125        if (optind != argc - 1) {
126            usage(argv[0]);
127            exit(EXIT_FAILURE);
128        }
129
130        pids = malloc(sizeof(*pids));
131        if (pids == NULL) {
132           fprintf(stderr, "Error allocating pid memory\n");
133           exit(EXIT_FAILURE);
134        }
135
136        *pids = strtoul(argv[optind], NULL, 10);
137        if (*pids == 0) {
138            fprintf(stderr, "Invalid PID\n");
139            rc = EXIT_FAILURE;
140            goto exit;
141        }
142        num_procs = 1;
143        if (getprocname(*pids, cmdline, sizeof(cmdline)) < 0) {
144            cmdline[0] = '\0';
145        }
146        printf("%s (%u):\n", cmdline, *pids);
147    }
148
149    printf("Warning: this tool only compares the KSM CRCs of pages, there is a chance of "
150            "collisions\n");
151
152    for (i = 0; i < num_procs; i++) {
153        error = pm_process_create(ker, pids[i], &proc);
154        if (error) {
155            fprintf(stderr, "warning: could not create process interface for %d\n", pids[i]);
156            rc = EXIT_FAILURE;
157            goto exit;
158        }
159
160        error = pm_process_maps(proc, &maps, &num_maps);
161        if (error) {
162            pm_process_destroy(proc);
163            fprintf(stderr, "warning: could not read process map for %d\n", pids[i]);
164            rc = EXIT_FAILURE;
165            goto exit;
166        }
167
168        if (read_pages(&kp, maps, num_maps, pr_flags) < 0) {
169            free(maps);
170            pm_process_destroy(proc);
171            rc = EXIT_FAILURE;
172            goto exit;
173        }
174
175        free(maps);
176        pm_process_destroy(proc);
177    }
178
179    if (pr_flags & PR_SORTED) {
180        qsort(kp.pages, kp.len, sizeof(*kp.pages), cmp_pages);
181    }
182    print_pages(&kp, pr_flags);
183
184exit:
185    free_pages(&kp, pr_flags);
186    free(pids);
187    return rc;
188}
189
190static int read_pages(struct ksm_pages *kp, pm_map_t **maps, size_t num_maps, uint8_t pr_flags) {
191    size_t i, j, k;
192    size_t len;
193    uint64_t *pagemap;
194    size_t map_len;
195    uint64_t flags;
196    pm_kernel_t *ker;
197    int error;
198    unsigned long vaddr;
199    int fd;
200    off_t off;
201    char filename[MAX_FILENAME];
202    uint32_t *data;
203    uint32_t hash;
204    int rc = 0;
205    struct ksm_page *cur_page;
206    pid_t pid;
207
208    if (num_maps == 0)
209        return 0;
210
211    pid = pm_process_pid(maps[0]->proc);
212    ker = maps[0]->proc->ker;
213    error = snprintf(filename, MAX_FILENAME, "/proc/%d/mem", pid);
214    if (error < 0 || error >= MAX_FILENAME) {
215        return -1;
216    }
217
218    data = malloc(pm_kernel_pagesize(ker));
219    if (data == NULL) {
220        fprintf(stderr, "warning: not enough memory to malloc data buffer\n");
221        return -1;
222    }
223
224    fd = open(filename, O_RDONLY);
225    if (fd < 0) {
226        fprintf(stderr, "warning: could not open %s\n", filename);
227        rc = -1;
228        goto err_open;
229    }
230
231    for (i = 0; i < num_maps; i++) {
232        error = pm_map_pagemap(maps[i], &pagemap, &map_len);
233        if (error) {
234            fprintf(stderr, "warning: could not read the pagemap of %d\n",
235                    pm_process_pid(maps[i]->proc));
236            continue;
237        }
238        for (j = 0; j < map_len; j++) {
239            error = pm_kernel_flags(ker, PM_PAGEMAP_PFN(pagemap[j]), &flags);
240            if (error) {
241                fprintf(stderr, "warning: could not read flags for pfn at address 0x%016" PRIx64 "\n",
242                        pagemap[i]);
243                continue;
244            }
245            if (!(flags & PM_PAGE_KSM)) {
246                continue;
247            }
248            vaddr = pm_map_start(maps[i]) + j * pm_kernel_pagesize(ker);
249            off = lseek(fd, vaddr, SEEK_SET);
250            if (off == (off_t)-1) {
251                fprintf(stderr, "warning: could not lseek to 0x%08lx\n", vaddr);
252                continue;
253            }
254            len = read(fd, data, pm_kernel_pagesize(ker));
255            if (len != pm_kernel_pagesize(ker)) {
256                fprintf(stderr, "warning: could not read page at 0x%08lx\n", vaddr);
257                continue;
258            }
259
260            hash = hashword(data, pm_kernel_pagesize(ker) / sizeof(*data), 17);
261
262            for (k = 0; k < kp->len; k++) {
263                if (kp->pages[k].hash == hash) break;
264            }
265
266            if (k == kp->len) {
267                if (kp->len == kp->size) {
268                    struct ksm_page *tmp = realloc(kp->pages,
269                            (kp->size + GROWTH_FACTOR) * sizeof(*kp->pages));
270                    if (tmp == NULL) {
271                        fprintf(stderr, "warning: not enough memory to realloc pages struct\n");
272                        free(pagemap);
273                        rc = -1;
274                        goto err_realloc;
275                    }
276                    memset(&tmp[k], 0, sizeof(tmp[k]) * GROWTH_FACTOR);
277                    kp->pages = tmp;
278                    kp->size += GROWTH_FACTOR;
279                }
280                rc = pm_kernel_count(ker, PM_PAGEMAP_PFN(pagemap[j]), &kp->pages[kp->len].count);
281                if (rc) {
282                    fprintf(stderr, "error reading page count\n");
283                    free(pagemap);
284                    goto err_count;
285                }
286                kp->pages[kp->len].hash = hash;
287                kp->pages[kp->len].pattern =
288                        is_pattern((uint8_t *)data, pm_kernel_pagesize(ker)) ?
289                        (data[0] & 0xFF) : NO_PATTERN;
290                kp->len++;
291            }
292
293            cur_page = &kp->pages[k];
294
295            if (pr_flags & PR_VERBOSE) {
296                if (cur_page->vaddr_len > 0 &&
297                        cur_page->vaddr[cur_page->vaddr_len - 1].pid == pid &&
298                        cur_page->vaddr[cur_page->vaddr_len - 1].addr ==
299                        vaddr - (cur_page->vaddr[cur_page->vaddr_len - 1].num_pages *
300                        pm_kernel_pagesize(ker))) {
301                    cur_page->vaddr[cur_page->vaddr_len - 1].num_pages++;
302                } else {
303                    if (cur_page->vaddr_len == cur_page->vaddr_size) {
304                        struct vaddr *tmp = realloc(cur_page->vaddr,
305                                (cur_page->vaddr_size + GROWTH_FACTOR) * sizeof(*(cur_page->vaddr)));
306                        if (tmp == NULL) {
307                            fprintf(stderr, "warning: not enough memory to realloc vaddr array\n");
308                            free(pagemap);
309                            rc = -1;
310                            goto err_realloc;
311                        }
312                        memset(&tmp[cur_page->vaddr_len], 0, sizeof(tmp[cur_page->vaddr_len]) * GROWTH_FACTOR);
313                        cur_page->vaddr = tmp;
314                        cur_page->vaddr_size += GROWTH_FACTOR;
315                    }
316                    cur_page->vaddr[cur_page->vaddr_len].addr = vaddr;
317                    cur_page->vaddr[cur_page->vaddr_len].num_pages = 1;
318                    cur_page->vaddr[cur_page->vaddr_len].pid = pid;
319                    cur_page->vaddr_len++;
320                }
321            }
322            cur_page->vaddr_count++;
323        }
324        free(pagemap);
325    }
326    goto no_err;
327
328err_realloc:
329err_count:
330    if (pr_flags & PR_VERBOSE) {
331        for (i = 0; i < kp->len; i++) {
332            free(kp->pages[i].vaddr);
333        }
334    }
335    free(kp->pages);
336
337no_err:
338    close(fd);
339err_open:
340    free(data);
341    return rc;
342}
343
344static void print_pages(struct ksm_pages *kp, uint8_t pr_flags) {
345    size_t i, j, k;
346    char suffix[13];
347    int index;
348
349    for (i = 0; i < kp->len; i++) {
350        if (kp->pages[i].pattern != NO_PATTERN) {
351            printf("0x%02x byte pattern: ", kp->pages[i].pattern);
352        } else {
353            printf("KSM CRC 0x%08x:", kp->pages[i].hash);
354        }
355        printf(" %4zu page", kp->pages[i].vaddr_count);
356        if (kp->pages[i].vaddr_count > 1) {
357            printf("s");
358        }
359        if (!(pr_flags & PR_ALL)) {
360            printf(" (%" PRIu64 " reference", kp->pages[i].count);
361            if (kp->pages[i].count > 1) {
362                printf("s");
363            }
364            printf(")");
365        }
366        printf("\n");
367
368        if (pr_flags & PR_VERBOSE) {
369            j = 0;
370            while (j < kp->pages[i].vaddr_len) {
371                printf("                   ");
372                for (k = 0; k < 8 && j < kp->pages[i].vaddr_len; k++, j++) {
373                    printf(" 0x%08lx", kp->pages[i].vaddr[j].addr);
374
375                    index = snprintf(suffix, sizeof(suffix), ":%zu",
376                            kp->pages[i].vaddr[j].num_pages);
377                    if (pr_flags & PR_ALL) {
378                        index += snprintf(suffix + index, sizeof(suffix) - index, "[%d]",
379                                kp->pages[i].vaddr[j].pid);
380                    }
381                    printf("%-12s", suffix);
382                }
383                printf("\n");
384            }
385        }
386    }
387}
388
389static void free_pages(struct ksm_pages *kp, uint8_t pr_flags) {
390    size_t i;
391
392    if (pr_flags & PR_VERBOSE) {
393        for (i = 0; i < kp->len; i++) {
394            free(kp->pages[i].vaddr);
395        }
396    }
397    free(kp->pages);
398}
399
400static void usage(char *myname) {
401    fprintf(stderr, "Usage: %s [-s | -v | -a | -h ] <pid>\n"
402                    "    -s  Sort pages by usage count.\n"
403                    "    -v  Verbose: print virtual addresses.\n"
404                    "    -a  Display all the KSM pages in the system. Ignore the pid argument.\n"
405                    "    -h  Display this help screen.\n",
406    myname);
407}
408
409static int cmp_pages(const void *a, const void *b) {
410    const struct ksm_page *pg_a = a;
411    const struct ksm_page *pg_b = b;
412    int cmp = pg_b->vaddr_count - pg_a->vaddr_count;
413
414    return cmp ? cmp : pg_b->count - pg_a->count;
415}
416
417static bool is_pattern(uint8_t *data, size_t len) {
418    size_t i;
419    uint8_t first_byte = data[0];
420
421    for (i = 1; i < len; i++) {
422        if (first_byte != data[i]) return false;
423    }
424
425    return true;
426}
427
428/*
429 * Get the process name for a given PID. Inserts the process name into buffer
430 * buf of length len. The size of the buffer must be greater than zero to get
431 * any useful output.
432 *
433 * Note that fgets(3) only declares length as an int, so our buffer size is
434 * also declared as an int.
435 *
436 * Returns 0 on success, a positive value on partial success, and -1 on
437 * failure. Other interesting values:
438 *   1 on failure to create string to examine proc cmdline entry
439 *   2 on failure to open proc cmdline entry
440 *   3 on failure to read proc cmdline entry
441 */
442static int getprocname(pid_t pid, char *buf, int len) {
443    char *filename;
444    FILE *f;
445    int rc = 0;
446    static const char* unknown_cmdline = "<unknown>";
447
448    if (len <= 0) {
449        return -1;
450    }
451
452    if (asprintf(&filename, "/proc/%d/cmdline", (int)pid) < 0) {
453        rc = 1;
454        goto exit;
455    }
456
457    f = fopen(filename, "r");
458    if (f == NULL) {
459        rc = 2;
460        goto releasefilename;
461    }
462
463    if (fgets(buf, len, f) == NULL) {
464        rc = 3;
465        goto closefile;
466    }
467
468closefile:
469    (void) fclose(f);
470releasefilename:
471    free(filename);
472exit:
473    if (rc != 0) {
474        /*
475         * The process went away before we could read its process name. Try
476         * to give the user "<unknown>" here, but otherwise they get to look
477         * at a blank.
478         */
479        if (strlcpy(buf, unknown_cmdline, (size_t)len) >= (size_t)len) {
480            rc = 4;
481        }
482    }
483
484    return rc;
485}
486
487