1 /*
2  * Copyright (C) 2016 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 <assert.h>
18 #include <stdint.h>
19 
20 #include <deque>
21 #include <string>
22 
23 #include <android-base/stringprintf.h>
24 
25 #include "ArmExidx.h"
26 #include "Log.h"
27 #include "Machine.h"
28 #include "Memory.h"
29 #include "Regs.h"
30 
LogRawData()31 void ArmExidx::LogRawData() {
32   std::string log_str("Raw Data:");
33   for (const uint8_t data : data_) {
34     log_str += android::base::StringPrintf(" 0x%02x", data);
35   }
36   log(log_indent_, log_str.c_str());
37 }
38 
ExtractEntryData(uint32_t entry_offset)39 bool ArmExidx::ExtractEntryData(uint32_t entry_offset) {
40   data_.clear();
41   status_ = ARM_STATUS_NONE;
42 
43   if (entry_offset & 1) {
44     // The offset needs to be at least two byte aligned.
45     status_ = ARM_STATUS_INVALID_ALIGNMENT;
46     return false;
47   }
48 
49   // Each entry is a 32 bit prel31 offset followed by 32 bits
50   // of unwind information. If bit 31 of the unwind data is zero,
51   // then this is a prel31 offset to the start of the unwind data.
52   // If the unwind data is 1, then this is a cant unwind entry.
53   // Otherwise, this data is the compact form of the unwind information.
54   uint32_t data;
55   if (!elf_memory_->Read32(entry_offset + 4, &data)) {
56     status_ = ARM_STATUS_READ_FAILED;
57     return false;
58   }
59   if (data == 1) {
60     // This is a CANT UNWIND entry.
61     status_ = ARM_STATUS_NO_UNWIND;
62     if (log_) {
63       log(log_indent_, "Raw Data: 0x00 0x00 0x00 0x01");
64       log(log_indent_, "[cantunwind]");
65     }
66     return false;
67   }
68 
69   if (data & (1UL << 31)) {
70     // This is a compact table entry.
71     if ((data >> 24) & 0xf) {
72       // This is a non-zero index, this code doesn't support
73       // other formats.
74       status_ = ARM_STATUS_INVALID_PERSONALITY;
75       return false;
76     }
77     data_.push_back((data >> 16) & 0xff);
78     data_.push_back((data >> 8) & 0xff);
79     uint8_t last_op = data & 0xff;
80     data_.push_back(last_op);
81     if (last_op != ARM_OP_FINISH) {
82       // If this didn't end with a finish op, add one.
83       data_.push_back(ARM_OP_FINISH);
84     }
85     if (log_) {
86       LogRawData();
87     }
88     return true;
89   }
90 
91   // Get the address of the ops.
92   // Sign extend the data value if necessary.
93   int32_t signed_data = static_cast<int32_t>(data << 1) >> 1;
94   uint32_t addr = (entry_offset + 4) + signed_data;
95   if (!elf_memory_->Read32(addr, &data)) {
96     status_ = ARM_STATUS_READ_FAILED;
97     return false;
98   }
99 
100   size_t num_table_words;
101   if (data & (1UL << 31)) {
102     // Compact model.
103     switch ((data >> 24) & 0xf) {
104     case 0:
105       num_table_words = 0;
106       data_.push_back((data >> 16) & 0xff);
107       break;
108     case 1:
109     case 2:
110       num_table_words = (data >> 16) & 0xff;
111       addr += 4;
112       break;
113     default:
114       // Only a personality of 0, 1, 2 is valid.
115       status_ = ARM_STATUS_INVALID_PERSONALITY;
116       return false;
117     }
118     data_.push_back((data >> 8) & 0xff);
119     data_.push_back(data & 0xff);
120   } else {
121     // Generic model.
122 
123     // Skip the personality routine data, it doesn't contain any data
124     // needed to decode the unwind information.
125     addr += 4;
126     if (!elf_memory_->Read32(addr, &data)) {
127       status_ = ARM_STATUS_READ_FAILED;
128       return false;
129     }
130     num_table_words = (data >> 24) & 0xff;
131     data_.push_back((data >> 16) & 0xff);
132     data_.push_back((data >> 8) & 0xff);
133     data_.push_back(data & 0xff);
134     addr += 4;
135   }
136 
137   if (num_table_words > 5) {
138     status_ = ARM_STATUS_MALFORMED;
139     return false;
140   }
141 
142   for (size_t i = 0; i < num_table_words; i++) {
143     if (!elf_memory_->Read32(addr, &data)) {
144       status_ = ARM_STATUS_READ_FAILED;
145       return false;
146     }
147     data_.push_back((data >> 24) & 0xff);
148     data_.push_back((data >> 16) & 0xff);
149     data_.push_back((data >> 8) & 0xff);
150     data_.push_back(data & 0xff);
151     addr += 4;
152   }
153 
154   if (data_.back() != ARM_OP_FINISH) {
155     // If this didn't end with a finish op, add one.
156     data_.push_back(ARM_OP_FINISH);
157   }
158 
159   if (log_) {
160     LogRawData();
161   }
162   return true;
163 }
164 
GetByte(uint8_t * byte)165 inline bool ArmExidx::GetByte(uint8_t* byte) {
166   if (data_.empty()) {
167     status_ = ARM_STATUS_TRUNCATED;
168     return false;
169   }
170   *byte = data_.front();
171   data_.pop_front();
172   return true;
173 }
174 
DecodePrefix_10_00(uint8_t byte)175 inline bool ArmExidx::DecodePrefix_10_00(uint8_t byte) {
176   assert((byte >> 4) == 0x8);
177 
178   uint16_t registers = (byte & 0xf) << 8;
179   if (!GetByte(&byte)) {
180     return false;
181   }
182 
183   registers |= byte;
184   if (registers == 0) {
185     // 10000000 00000000: Refuse to unwind
186     if (log_) {
187       log(log_indent_, "Refuse to unwind");
188     }
189     status_ = ARM_STATUS_NO_UNWIND;
190     return false;
191   }
192   // 1000iiii iiiiiiii: Pop up to 12 integer registers under masks {r15-r12}, {r11-r4}
193   if (log_) {
194     bool add_comma = false;
195     std::string msg = "pop {";
196     for (size_t i = 0; i < 12; i++) {
197       if (registers & (1 << i)) {
198         if (add_comma) {
199           msg += ", ";
200         }
201         msg += android::base::StringPrintf("r%zu", i + 4);
202         add_comma = true;
203       }
204     }
205     log(log_indent_, "%s}", msg.c_str());
206     if (log_skip_execution_) {
207       return true;
208     }
209   }
210 
211   registers <<= 4;
212   for (size_t reg = 4; reg < 16; reg++) {
213     if (registers & (1 << reg)) {
214       if (!process_memory_->Read32(cfa_, &(*regs_)[reg])) {
215         status_ = ARM_STATUS_READ_FAILED;
216         return false;
217       }
218       cfa_ += 4;
219     }
220   }
221 
222   // If the sp register is modified, change the cfa value.
223   if (registers & (1 << ARM_REG_SP)) {
224     cfa_ = (*regs_)[ARM_REG_SP];
225   }
226 
227   // Indicate if the pc register was set.
228   if (registers & (1 << ARM_REG_PC)) {
229     pc_set_ = true;
230   }
231   return true;
232 }
233 
DecodePrefix_10_01(uint8_t byte)234 inline bool ArmExidx::DecodePrefix_10_01(uint8_t byte) {
235   assert((byte >> 4) == 0x9);
236 
237   uint8_t bits = byte & 0xf;
238   if (bits == 13 || bits == 15) {
239     // 10011101: Reserved as prefix for ARM register to register moves
240     // 10011111: Reserved as prefix for Intel Wireless MMX register to register moves
241     if (log_) {
242       log(log_indent_, "[Reserved]");
243     }
244     status_ = ARM_STATUS_RESERVED;
245     return false;
246   }
247   // 1001nnnn: Set vsp = r[nnnn] (nnnn != 13, 15)
248   if (log_) {
249     log(log_indent_, "vsp = r%d", bits);
250     if (log_skip_execution_) {
251       return true;
252     }
253   }
254   // It is impossible for bits to be larger than the total number of
255   // arm registers, so don't bother checking if bits is a valid register.
256   cfa_ = (*regs_)[bits];
257   return true;
258 }
259 
DecodePrefix_10_10(uint8_t byte)260 inline bool ArmExidx::DecodePrefix_10_10(uint8_t byte) {
261   assert((byte >> 4) == 0xa);
262 
263   // 10100nnn: Pop r4-r[4+nnn]
264   // 10101nnn: Pop r4-r[4+nnn], r14
265   if (log_) {
266     std::string msg = "pop {r4";
267     uint8_t end_reg = byte & 0x7;
268     if (end_reg) {
269       msg += android::base::StringPrintf("-r%d", 4 + end_reg);
270     }
271     if (byte & 0x8) {
272       log(log_indent_, "%s, r14}", msg.c_str());
273     } else {
274       log(log_indent_, "%s}", msg.c_str());
275     }
276     if (log_skip_execution_) {
277       return true;
278     }
279   }
280 
281   for (size_t i = 4; i <= 4 + (byte & 0x7); i++) {
282     if (!process_memory_->Read32(cfa_, &(*regs_)[i])) {
283       status_ = ARM_STATUS_READ_FAILED;
284       return false;
285     }
286     cfa_ += 4;
287   }
288   if (byte & 0x8) {
289     if (!process_memory_->Read32(cfa_, &(*regs_)[ARM_REG_R14])) {
290       status_ = ARM_STATUS_READ_FAILED;
291       return false;
292     }
293     cfa_ += 4;
294   }
295   return true;
296 }
297 
DecodePrefix_10_11_0000()298 inline bool ArmExidx::DecodePrefix_10_11_0000() {
299   // 10110000: Finish
300   if (log_) {
301     log(log_indent_, "finish");
302     if (log_skip_execution_) {
303       status_ = ARM_STATUS_FINISH;
304       return false;
305     }
306   }
307   status_ = ARM_STATUS_FINISH;
308   return false;
309 }
310 
DecodePrefix_10_11_0001()311 inline bool ArmExidx::DecodePrefix_10_11_0001() {
312   uint8_t byte;
313   if (!GetByte(&byte)) {
314     return false;
315   }
316 
317   if (byte == 0) {
318     // 10110001 00000000: Spare
319     if (log_) {
320       log(log_indent_, "Spare");
321     }
322     status_ = ARM_STATUS_SPARE;
323     return false;
324   }
325   if (byte >> 4) {
326     // 10110001 xxxxyyyy: Spare (xxxx != 0000)
327     if (log_) {
328       log(log_indent_, "Spare");
329     }
330     status_ = ARM_STATUS_SPARE;
331     return false;
332   }
333 
334   // 10110001 0000iiii: Pop integer registers under mask {r3, r2, r1, r0}
335   if (log_) {
336     bool add_comma = false;
337     std::string msg = "pop {";
338     for (size_t i = 0; i < 4; i++) {
339       if (byte & (1 << i)) {
340         if (add_comma) {
341           msg += ", ";
342         }
343         msg += android::base::StringPrintf("r%zu", i);
344         add_comma = true;
345       }
346     }
347     log(log_indent_, "%s}", msg.c_str());
348     if (log_skip_execution_) {
349       return true;
350     }
351   }
352 
353   for (size_t reg = 0; reg < 4; reg++) {
354     if (byte & (1 << reg)) {
355       if (!process_memory_->Read32(cfa_, &(*regs_)[reg])) {
356         status_ = ARM_STATUS_READ_FAILED;
357         return false;
358       }
359       cfa_ += 4;
360     }
361   }
362   return true;
363 }
364 
DecodePrefix_10_11_0010()365 inline bool ArmExidx::DecodePrefix_10_11_0010() {
366   // 10110010 uleb128: vsp = vsp + 0x204 + (uleb128 << 2)
367   uint32_t result = 0;
368   uint32_t shift = 0;
369   uint8_t byte;
370   do {
371     if (!GetByte(&byte)) {
372       return false;
373     }
374 
375     result |= (byte & 0x7f) << shift;
376     shift += 7;
377   } while (byte & 0x80);
378   result <<= 2;
379   if (log_) {
380     log(log_indent_, "vsp = vsp + %d", 0x204 + result);
381     if (log_skip_execution_) {
382       return true;
383     }
384   }
385   cfa_ += 0x204 + result;
386   return true;
387 }
388 
DecodePrefix_10_11_0011()389 inline bool ArmExidx::DecodePrefix_10_11_0011() {
390   // 10110011 sssscccc: Pop VFP double precision registers D[ssss]-D[ssss+cccc] by FSTMFDX
391   uint8_t byte;
392   if (!GetByte(&byte)) {
393     return false;
394   }
395 
396   if (log_) {
397     uint8_t start_reg = byte >> 4;
398     std::string msg = android::base::StringPrintf("pop {d%d", start_reg);
399     uint8_t end_reg = start_reg + (byte & 0xf);
400     if (end_reg) {
401       msg += android::base::StringPrintf("-d%d", end_reg);
402     }
403     log(log_indent_, "%s}", msg.c_str());
404     if (log_skip_execution_) {
405       return true;
406     }
407   }
408   cfa_ += (byte & 0xf) * 8 + 12;
409   return true;
410 }
411 
DecodePrefix_10_11_01nn()412 inline bool ArmExidx::DecodePrefix_10_11_01nn() {
413   // 101101nn: Spare
414   if (log_) {
415     log(log_indent_, "Spare");
416   }
417   status_ = ARM_STATUS_SPARE;
418   return false;
419 }
420 
DecodePrefix_10_11_1nnn(uint8_t byte)421 inline bool ArmExidx::DecodePrefix_10_11_1nnn(uint8_t byte) {
422   assert((byte & ~0x07) == 0xb8);
423 
424   // 10111nnn: Pop VFP double-precision registers D[8]-D[8+nnn] by FSTMFDX
425   if (log_) {
426     std::string msg = "pop {d8";
427     uint8_t last_reg = (byte & 0x7);
428     if (last_reg) {
429       msg += android::base::StringPrintf("-d%d", last_reg + 8);
430     }
431     log(log_indent_, "%s}", msg.c_str());
432     if (log_skip_execution_) {
433       return true;
434     }
435   }
436   // Only update the cfa.
437   cfa_ += (byte & 0x7) * 8 + 12;
438   return true;
439 }
440 
DecodePrefix_10(uint8_t byte)441 inline bool ArmExidx::DecodePrefix_10(uint8_t byte) {
442   assert((byte >> 6) == 0x2);
443 
444   switch ((byte >> 4) & 0x3) {
445   case 0:
446     return DecodePrefix_10_00(byte);
447   case 1:
448     return DecodePrefix_10_01(byte);
449   case 2:
450     return DecodePrefix_10_10(byte);
451   default:
452     switch (byte & 0xf) {
453     case 0:
454       return DecodePrefix_10_11_0000();
455     case 1:
456       return DecodePrefix_10_11_0001();
457     case 2:
458       return DecodePrefix_10_11_0010();
459     case 3:
460       return DecodePrefix_10_11_0011();
461     default:
462       if (byte & 0x8) {
463         return DecodePrefix_10_11_1nnn(byte);
464       } else {
465         return DecodePrefix_10_11_01nn();
466       }
467     }
468   }
469 }
470 
DecodePrefix_11_000(uint8_t byte)471 inline bool ArmExidx::DecodePrefix_11_000(uint8_t byte) {
472   assert((byte & ~0x07) == 0xc0);
473 
474   uint8_t bits = byte & 0x7;
475   if (bits == 6) {
476     if (!GetByte(&byte)) {
477       return false;
478     }
479 
480     // 11000110 sssscccc: Intel Wireless MMX pop wR[ssss]-wR[ssss+cccc]
481     if (log_) {
482       uint8_t start_reg = byte >> 4;
483       std::string msg = android::base::StringPrintf("pop {wR%d", start_reg);
484       uint8_t end_reg = byte & 0xf;
485       if (end_reg) {
486         msg += android::base::StringPrintf("-wR%d", start_reg + end_reg);
487       }
488       log(log_indent_, "%s}", msg.c_str());
489       if (log_skip_execution_) {
490         return true;
491       }
492     }
493     // Only update the cfa.
494     cfa_ += (byte & 0xf) * 8 + 8;
495   } else if (bits == 7) {
496     if (!GetByte(&byte)) {
497       return false;
498     }
499 
500     if (byte == 0) {
501       // 11000111 00000000: Spare
502       if (log_) {
503         log(log_indent_, "Spare");
504       }
505       status_ = ARM_STATUS_SPARE;
506       return false;
507     } else if ((byte >> 4) == 0) {
508       // 11000111 0000iiii: Intel Wireless MMX pop wCGR registers {wCGR0,1,2,3}
509       if (log_) {
510         bool add_comma = false;
511         std::string msg = "pop {";
512         for (size_t i = 0; i < 4; i++) {
513           if (byte & (1 << i)) {
514             if (add_comma) {
515               msg += ", ";
516             }
517             msg += android::base::StringPrintf("wCGR%zu", i);
518             add_comma = true;
519           }
520         }
521         log(log_indent_, "%s}", msg.c_str());
522       }
523       // Only update the cfa.
524       cfa_ += __builtin_popcount(byte) * 4;
525     } else {
526       // 11000111 xxxxyyyy: Spare (xxxx != 0000)
527       if (log_) {
528         log(log_indent_, "Spare");
529       }
530       status_ = ARM_STATUS_SPARE;
531       return false;
532     }
533   } else {
534     // 11000nnn: Intel Wireless MMX pop wR[10]-wR[10+nnn] (nnn != 6, 7)
535     if (log_) {
536       std::string msg = "pop {wR10";
537       uint8_t nnn = byte & 0x7;
538       if (nnn) {
539         msg += android::base::StringPrintf("-wR%d", 10 + nnn);
540       }
541       log(log_indent_, "%s}", msg.c_str());
542       if (log_skip_execution_) {
543         return true;
544       }
545     }
546     // Only update the cfa.
547     cfa_ += (byte & 0x7) * 8 + 8;
548   }
549   return true;
550 }
551 
DecodePrefix_11_001(uint8_t byte)552 inline bool ArmExidx::DecodePrefix_11_001(uint8_t byte) {
553   assert((byte & ~0x07) == 0xc8);
554 
555   uint8_t bits = byte & 0x7;
556   if (bits == 0) {
557     // 11001000 sssscccc: Pop VFP double precision registers D[16+ssss]-D[16+ssss+cccc] by VPUSH
558     if (!GetByte(&byte)) {
559       return false;
560     }
561 
562     if (log_) {
563       uint8_t start_reg = byte >> 4;
564       std::string msg = android::base::StringPrintf("pop {d%d", 16 + start_reg);
565       uint8_t end_reg = byte & 0xf;
566       if (end_reg) {
567         msg += android::base::StringPrintf("-d%d", 16 + start_reg + end_reg);
568       }
569       log(log_indent_, "%s}", msg.c_str());
570       if (log_skip_execution_) {
571         return true;
572       }
573     }
574     // Only update the cfa.
575     cfa_ += (byte & 0xf) * 8 + 8;
576   } else if (bits == 1) {
577     // 11001001 sssscccc: Pop VFP double precision registers D[ssss]-D[ssss+cccc] by VPUSH
578     if (!GetByte(&byte)) {
579       return false;
580     }
581 
582     if (log_) {
583       uint8_t start_reg = byte >> 4;
584       std::string msg = android::base::StringPrintf("pop {d%d", start_reg);
585       uint8_t end_reg = byte & 0xf;
586       if (end_reg) {
587         msg += android::base::StringPrintf("-d%d", start_reg + end_reg);
588       }
589       log(log_indent_, "%s}", msg.c_str());
590       if (log_skip_execution_) {
591         return true;
592       }
593     }
594     // Only update the cfa.
595     cfa_ += (byte & 0xf) * 8 + 8;
596   } else {
597     // 11001yyy: Spare (yyy != 000, 001)
598     if (log_) {
599       log(log_indent_, "Spare");
600     }
601     status_ = ARM_STATUS_SPARE;
602     return false;
603   }
604   return true;
605 }
606 
DecodePrefix_11_010(uint8_t byte)607 inline bool ArmExidx::DecodePrefix_11_010(uint8_t byte) {
608   assert((byte & ~0x07) == 0xd0);
609 
610   // 11010nnn: Pop VFP double precision registers D[8]-D[8+nnn] by VPUSH
611   if (log_) {
612     std::string msg = "pop {d8";
613     uint8_t end_reg = byte & 0x7;
614     if (end_reg) {
615       msg += android::base::StringPrintf("-d%d", 8 + end_reg);
616     }
617     log(log_indent_, "%s}", msg.c_str());
618     if (log_skip_execution_) {
619       return true;
620     }
621   }
622   cfa_ += (byte & 0x7) * 8 + 8;
623   return true;
624 }
625 
DecodePrefix_11(uint8_t byte)626 inline bool ArmExidx::DecodePrefix_11(uint8_t byte) {
627   assert((byte >> 6) == 0x3);
628 
629   switch ((byte >> 3) & 0x7) {
630   case 0:
631     return DecodePrefix_11_000(byte);
632   case 1:
633     return DecodePrefix_11_001(byte);
634   case 2:
635     return DecodePrefix_11_010(byte);
636   default:
637     // 11xxxyyy: Spare (xxx != 000, 001, 010)
638     if (log_) {
639       log(log_indent_, "Spare");
640     }
641     status_ = ARM_STATUS_SPARE;
642     return false;
643   }
644 }
645 
Decode()646 bool ArmExidx::Decode() {
647   status_ = ARM_STATUS_NONE;
648   uint8_t byte;
649   if (!GetByte(&byte)) {
650     return false;
651   }
652 
653   switch (byte >> 6) {
654   case 0:
655     // 00xxxxxx: vsp = vsp + (xxxxxxx << 2) + 4
656     if (log_) {
657       log(log_indent_, "vsp = vsp + %d", ((byte & 0x3f) << 2) + 4);
658       if (log_skip_execution_) {
659         break;
660       }
661     }
662     cfa_ += ((byte & 0x3f) << 2) + 4;
663     break;
664   case 1:
665     // 01xxxxxx: vsp = vsp - (xxxxxxx << 2) + 4
666     if (log_) {
667       log(log_indent_, "vsp = vsp - %d", ((byte & 0x3f) << 2) + 4);
668       if (log_skip_execution_) {
669         break;
670       }
671     }
672     cfa_ -= ((byte & 0x3f) << 2) + 4;
673     break;
674   case 2:
675     return DecodePrefix_10(byte);
676   default:
677     return DecodePrefix_11(byte);
678   }
679   return true;
680 }
681 
Eval()682 bool ArmExidx::Eval() {
683   pc_set_ = false;
684   while (Decode());
685   return status_ == ARM_STATUS_FINISH;
686 }
687